ArrayList와 LinkedList 차이

List

List Interface(리스트 인터페이스)는 대표적인 선형 자료구조로 주로 순서가 있는 데이터를 목록으로 이용할 수 있도록 만들어진 인터페이스다. 우리가 배열을 사용할 때 int[] array = new int[10];처럼 사용하지만 이러한 경우는 10개의 공간 외에는 더이상 사용하지 못한다. 만약 array[13] = 30;가 실행되면 할당된 크기(범위) 밖이기 때문에 IndexOutofBoundsException라는 에러가 발생한다.

이러한 단점을 보완하여 List를 통해 구현된 클래스들은 '동적 크기'를 갖으며 배열처럼 사용할 수 있게 되어있다. 한 마디로 배열의 기능 + 동적 크기 할당이 합쳐져 있다고 보면 된다.

 

List Interface에 선언된 대표적인 메서드

메서드	리턴 타입	설명
add(E e)	boolean	요소를 추가한다.
remove(Object o)	boolean	지정한 객체와 같은 첫 번째 객체를 삭제한다.
contains(Object o)	boolean	지정한 객체가 컬렉션에 있는지를 확인한다. (있을 경우 true, 없을 경우 false)
size()	int	현재 컬렉션에 있는 요소 개수를 반환한다.
get(int index)	E	지정된 위치에 저장된 원소를 반환한다.
set(int index, E elements)	E	지정된 위치에 있는 요소를 지정된 요소로 바꾼다.
isEmpty()	boolean	현재 컬렉션에 요소가 없다면 true를, 요소가 존재한다면 false를 반환한다.
equals(Object o)	boolean	지정된 객체와 같은지 비교한다.
indexOf(Object o)	int	지정된 객체가 있는 첫 번째 요소의 위치를 반환한다. 만일 없을경우 -1을 반환한다.
clear()	void	모든 요소들을 제거한다.

 

List와 Array의 차이점

동일한 특성의 데이터를 묶고, 반복문(loop) 내에 변수를 이용하여 하나의 묶음 데이터들을 모두 접근할 수 있는 공통점이 있지만 다음과 같은 차이점이 있다.

 

Array

• 처음 선언한 배열의 크기(길이)는 변경할 수 없다. 이를 정적 할당(static allocation)이라고 한다.
• 메모리에 연속적으로 나열되어 할당된다.
• index에 위치한 하나의 데이터(element)를 삭제하더라도 해당 index에는 빈공간으로 계속 남는다.

 

List

• 리스트의 길이가 가변적이다. 이를 동적 할당(dynamic allocation)이라고 한다.
• 데이터들이 연속적으로 나열된다.(메모리에 연속적으로 나열되지 않고 각 데이터들은 주소(reference)로 연결되어있다.)
• 데이터(element) 사이에 빈 공간을 허용하지 않는다.

 

ArrayList

ArrayList는 Object[] 배열을 사용하면서 내부 구현을 통해 동적으로 관리를 한다. 우리가 흔히 쓰는 Primitive 배열(ex. int[])과 유사한 형태라고 보면 된다. 하지만 Array와는 달리 데이터가 추가하는대로 필요시 2배로 사이즈가 늘어난다. 즉, 최상위 타입인 Object 타입으로 배열을 생성하여 사용하기 때문에 요소 접근(access elements)에서는 탁월한 성능을 보인다. 그 이유는 사이즈는 늘어나지만 검색할 때는 고정된 배열크기에서 검색을 하는 덕분에 O(1)이다. 하지만 중간의 요소가 삽입, 삭제가 일어나는 경우 그 뒤의 요소들은 한 칸씩 밀어야 하거나 당겨야 하기 때문에 삽입, 삭제에서는 비효율적인 모습을 보인다.

 

ArrayList 구현하기

public class MyArrayList {

    private Object[] data;
    private int size; // 배열의 크기
    private int index; // 다음 데이터를 추가할 위치를 기억

    public MyArrayList() {
        this.size = 1; // MyArrayList 객체를 생성하면 먼저 사이즈 1로 할당
        this.data = new Object[this.size]; // size만큼 배열크기 생성
        this.index = 0;
    }

    public void add(Object obj) {
        System.out.println("index: " + index + ", size: " + size + ", datasize: " + data.length + ", obj: " + obj);
        // 추가 전에 배열 크기가 다 찼는지 확인
        if (index == size - 1) {
            doubling();
        }

        data[this.index] = obj;
        index++;
    }

    public Object get(int i) throws Exception {
        if (i > index - 1) {
            throw new Exception("ArrayIndexOutOfBound");
        } else if (i < 0) {
            throw new Exception("Negative Value");
        }

        return data[i];
    }

    public void remove(int i) throws Exception {
        if (i > index - 1) {
            throw new Exception("ArrayIndexOutOfBound");
        } else if (i < 0) {
            throw new Exception("Negative Value");
        }

        // 삭제할 데이터를 기준으로 한 칸씩 앞으로 shift해서 빈 자리를 메꿔줌
        for (int x = i; x < data.length - 1; x++) {
            data[x] = data[x + 1];
        }

        index--;
    }

    private void doubling() {
        size = size * 2;
        Object[] newData = new Object[this.size];

        // 새로운 배열에 기존 배열에 있는 데이터 복사하는 작업
        for(int i = 0; i < data.length; i++) {
            newData[i] = data[i];
        }

        this.data = newData;
    }
}

 

ArrayList는 필요시 사이즈가 늘어날 때 2배 큰 크기의 새로운 배열을 선언하고, 그 배열에 기존 배열에 있었던 데이터 전부 를 새로운 배열에 복사하는 작업을 하는데 이를 Doubling이라고 한다. 이 Doubling에 소요되는 시간은 기존에 가지고 있었던 데이터를 N이라고 할 때 O(N)의 시간이 소요된다. 이런 번거로운 작업에도 불구하고, ArrayList의 입력시간은 여전히 O(1)이다. 그 이유는 Doubling을 할 때 그 전에 있던 데이터는 절반이기 때문에 

 

MyArrayList 실행

public class Test {

    public static void main(String[] args) throws Exception {
        MyArrayList arrayList = new MyArrayList();
        arrayList.add("0");
        arrayList.add("1");
        arrayList.add("2");
        arrayList.add("3");
        arrayList.add("4");
        arrayList.add("5");
        arrayList.add("6");
        arrayList.add("7");
        arrayList.add("8");
        arrayList.add("9");
        System.out.println(arrayList.get(5));
        arrayList.remove(5);
        System.out.println(arrayList.get(5));
    }
}

위에서 설명했듯이 만약 데이터를 추가할 때 모두 차면 새로운 데이터 배열에 기존 데이터를 복사해야하기 때문에 O(N)이 시간이 걸리게 되고, 그 외에는 O(1)의 시간이 걸리게 된다.

 

LinkedList

LinkedList는 데이터(item)와 주소로 이루어진 클래스를 만들어 서로 연결하는 방식이다. 데이터와 주소로 이루어진 클래스를 Node(노드)라고 하는데, 각 노드는 이전의 노드와 다음 노드를 연결하는 방식이다. LinkedList의 경우 ArrayList와 가장 큰 차이점이라고 한다면 '노드'라는 객체를 이용하여 연결한다는 것이다.

 

출처 - 자바 [Java] - Singly LinkedList(단일 연결리스트) 구현하기

ArrayList는 최상위 타입인 오브젝트 배열(Object[])을 사용하여 데이터를 담아두었다면, LinkedList는 배열을 이용하는 것이 아닌 하나의 객체를 두고 그 안에 데이터와 다른 노드를 가리키는 레퍼런스 데이터로 구성하여 여러 노드를 하나의 체인(chain)처럼 연결하는 것이다.

 

자세한 LinkedList에 대한 설명은 아래 블로그에서 보자.

LinkedList(SinglyLinkedList vs DoublyLinkedList)

 

ArrayList와 LinkedList 시간 복잡도 차이

작업	메서드	ArrayList	LinkedList
add at last index	add()	O(1)	O(1)
add at given index	add(index, value)	O(N)	O(1)
remove by index	remove(index)	O(N)	O(1)
remove by value	remove(value)	O(N)	O(1)
get by index	get(index)	O(1)	O(N)
search by value	indexOf(value)0	O(N)	O(N)

 

ArrayList와 LinkedList 비교 측정하기

public class CompareArrayListLinkedList {

  public static void main(String[] args) {
    long arrayListStart = System.currentTimeMillis();
    List<Integer> arrayList = new ArrayList<>();

    for (int i = 0; i < 1_000_000; i++) {
      arrayList.add(0, i);
    }
    long arrayListFinish = System.currentTimeMillis() - arrayListStart;

    long linkedListStart = System.currentTimeMillis();
    List<Integer> linkedList = new LinkedList<>();

    for (int i = 0; i < 1_000_000; i++) {
      linkedList.add(0, i);
    }
    long linkedListFinish = System.currentTimeMillis() - linkedListStart;

    System.out.println("arrayListFinish = " + arrayListFinish);
    System.out.println("linkedListFinish = " + linkedListFinish);
  }
}

ArayList를 1,000,000번 0번 인덱스에 넣는 작업을 한 결과 52.266초가 나오고, LinkedList에도 마찬가지로 0번 인덱스에 넣는 작업을 한 결과 0.063초가 나온것을 확인할 수 있다. ArrayList는 삽입하고 뒤 엘리먼트들을 모두 미는 작업도 해야하는 반면, LinkedList는  새로 들어온 노드를 head로 바꿔주고 next로 이전 head를 가리키는 작업만 하면 되기 때문에 성능에 차이가 있는 것을 확인할 수 있다.

 

ArrayList와 LinkedList 비교 측정 한계점

성능을 테스트하고 싶을 때는 startTime과 finishTime을 측정해서 테스트 결과를 비교하는데 로직 성능만을 검사하고 싶지만 warm up, 스레드 갯수 등 고려해야할 사항들이 많다. 이러한 부분을 해결해주기 위한 성능 측정 프레임워크인 벤치마크 프레임워크를 사용해서 로직에 대한 성능을 위해 부수적인 것들을 줄일 수 있는데 이에 대한 내용은 아래 글을 작성했으니 참고하자.

JMH로 warm up 후 테스트하기

 

 

출처

자바[JAVA] - 자바 컬렉션 프레임워크(Java Collections Framework)

자바[JAVA] - List Inteface(리스트 인터페이스)

자바[JAVA] - Singly LinkedList(단일 연결리스트) 구현하기