[자료구조] [Array, ArrayList] VS [LinkedList]

1. Array

배열의 크기는 처음 한번 정하면 변경할 수 없다. 

배열 초기화 시 메모리에 할당되어 ArrayList보다 속도가 빠르다.

논리적 저장 순서와 물리적 저장 순서가 일치한다. 따라서 인덱스로 해당 원소에 접근할 수 있다.

그렇기 때문에 찾고자 하는 원소의 인덱스 값을 알고있으면 O(1)로 원소에 접근할 수 있다. 즉, random access가 가능하다는 장점이 있다.

 

 

2. ArrayList

크기가 가변적이다.

저장하는 데이터 수에 따라서 크기가 변경된다.

데이터 추가, 삭제가 가능하지만 그마다 메모리를 재할당하기 때문에 속도가 배열보다 느리다.

n개의 자료를 저장할 때 ArrayList는 자료들을 하나의 연속적인 묶음으로 묶어 자료를 저장

무작위 접근 가능

사이즈 고정되어 있음

삽입 시, 사이즈를 늘려주는 연산이 추가되야 함.

지속적으로 삭제 되는 과정에서 공간만큼 낭비되는 메모리가 많음.

삽입 삭제가 빈번하게 발생하는 프로세스의 경우 좋지 않음.

 

3. LinkedList

연결형태로 연결 가능

ArrayList처럼 뒤로 밀거나 채우는 작업 없이 주소만 서로 연결시켜 주면 되기 때문에 추가 삭제가 ArrayList보다 빠르고 용이함.

삽입삭제가 빈번하게 발생되면 LinkedList를 사용해 시스템을 구현하는 것이 바람직함

순차접근(sequential access)만 가능

단순 LinkedList는 단방향성을 갖고 있어 인덱스를 사용해 자료를 검색하는 애플리케이션에 적합하지 않음.

순차 접근도 참조의 지역성(한번 참조한 데이터는 다시 참조될 가능성이 높음)때문에 LinkedList보다 ArrayList가 훨씬 빠름.

n개의 자료를 저장할 때 LinkedList는 자료들을 저장공간에 불연속적 단위로 저장

LinkedList는 메모리 이곳 저곳에 산재해 저장되어 있는 노드들을 접근하는데 ArrayList보다는 긴 지연 시간이 소모됌.

LinkedList는 참조자를 위해 추가적인 메모리를 할당해야함. (자료들의 크기가 작은 리스트의 경우 참조자를 위한 주가적인 메모리 할당은 비실용적임)

 

 

1부터 7까지 나열된 정수 ( 1, 2, 3, 4, 5, 6, 7 )를 묶어서 표현하는 방법은 다음과 같다.

배열(Array), 배열리스트(ArrayList), 연결리스트(LinkedList)

 

1. 배열

int[] arr = {1, 2, 3, 4, 5, 6, 7};

 

 

2. ArrayList

(java의 경우, java.util 패키지에 이미 구현되어져있는 ArrayList를 이용하여 객체 생성 후, add 혹은 remove)

import java.util.ArrayList;

List<Integer> arrList = new Arraylist<>();

for(int i=1; i<=7; i++){
   arrList.add(i);
}

 

3. LinkedList

 (java.util 패키지에 내장되어있는 LinkedList가 있다. 그렇지만 원리를 위해 직접 구현해보면 다음과 같다.)

package data_structure;

class Node {
    int data;
    Node next;
    Node(int data){
        this.data = data;
    }
}

//LinkedList의 틀을 추상화할 main class
public class SinglyLinkedList {
    Node head;

    public void add(int data){
        if(head == null){
            head = new Node(data);
            return;
        }

        while(head.next != null){
            head = head.next;
        }
        head.next = new Node(data);
    }

    public void remove(int data){
        // 배열에 아무것도 없을 경우
        if(head == null) return;
        // data가 맨 앞에 있을 경우.
        if(head.data == data) {
            head = head.next;
            return;
        }

        Node current = head;
        while(current.next != null) {
            if(current.next.data == data){
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }
    }

    public static void printSinglyLinkedList(SinglyLinkedList list){
        Node node = list.head;
        System.out.println(node.next.data);
//        while(node.next != null){
//            System.out.print(node.data + " ");
//            node = node.next;
//        }
//
//        if(node != null) System.out.print(node.data);

    }

    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();

        for(int i=1; i<=7; i++){
            list.add(i);
        }

        printSinglyLinkedList(list);

    }
}