[Java] ArrayList vs LinkedList

서론

List는 모든 언어에서 가장 유용한 자료구조 중 하나입니다. Java에서는 List를 인터페이스로 제공하며, LinkedList와 ArrayList를 구현하여 사용할 수 있습니다.

ArrayList와 LinkedList의 공통된 부분을 뽑아서 Colletion 인터페이스를 추가로 정의하였는데, 인터페이스만 같을 뿐 내부적으로 동작하는 방식은 다릅니다. 이번 게시글에서는 ArrayList와 LinkedList의 차이를 알아보고 어떠한 상황에서 사용해야 할지 알아보겠습니다.

 

ArrayList

ArrayList는 List 인터페이스를 구현하기 때문에 데이터의 저장순서가 유지되고 중복을 허용한다는 특징을 갖고 있습니다.

ArrayList는 기존의 Java Vector를 개선한 것으로 Vector와 구현 측면에서 동일하다고 할 수 있습니다. 하지만 현재로 와서 Vector는 기존에 작성된 소스와의 호환성을 위해서 계속 남겨 두고 있을 뿐이기 때문에 가능하면 Vector보다는 ArrayList를 사용하는 것이 좋습니다.

ArrayList는 Object 배열을 이용해서 데이터를 순차적으로 저장합니다. 만약 배열의 공간이 꽉 차 더 이상 저장할 공간이 없으면 기존의 배열보다 자동적으로 2배 더 큰 새로운 배열을 생성해서 기존의 배열에 저장된 내용을 새로운 배열로 복사한 다음에 저장합니다.

배열이 공간이 꽉 찼을 경우

 ArrayList는 삭제에서도 마찬가지로 복사 작업이 일어납니다.

배열의 원소 삭제

현재 배열에서  0~4의 값이 저장되어 있는 상태에서 세번 째 데이터(2)를 삭제하였다고 가정하면 복사 작업을 통해 모두 한 칸씩 위로 복사와 덮어 씌우기 작업이 일어나게 됩니다. 만약 배열에 객체를 중간에 삽입하는 것이 아닌 순차적으로 저장할 때와 객체를 마지막에 저장된 것부터 삭제하지 않는 이상은 복사 작업이 일어나기 때문에 다루는 데이터의 개수가 많을수록 작업시간이 오래 걸리게 됩니다.

따라서 ArrayList의 내용을 정리해 보자면 아래와 같습니다.

1. 크기를 변경할 수 없다.
    - 크기를 변경할 수 없으므로 새로운 배열을 생성해서 데이터를 복사해야 한다.
    - 실행속도를 향상하기 위해서는 충분히 큰 크기의 배열을 생성해야 하므로 메모리가 낭비될 수가 있다.
2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.
    - 차례대로 데이터를 추가하고 마지막에서부터 데이터를 삭제하는 것은 빠르지만, 
       배열의 중간에 데이터를 추가하려면 빈자리를 만들기 위해 다른 데이터들을 복사해서 이동해야 한다.

 

LinkedList

배열은 모든 데이터가 연속적으로 존재하지만 LinkedList는 불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성되어 있습니다.

배열과 링크드 리스트

위의 그림에서 알 수 있듯이 LinkedList의 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조(주소 값)와 데이터로 구성되어 있습니다. 

LinkedList에서의 데이터 삭제와 추가는 ArrayList와 다르게 간단합니다. 삭제하고자 하는 요소의 이전요소가 삭제하고자 하는 요소의 다음 요소를 참도하도록 변경하기만 하면 됩니다. 단 하나의 참조만 변경하면 삭제가 이루어지는 것입니다. 배열처럼 데이터를 이동하기 위해 복사하는 과정이 없기 때문에 처리속도가 매우 빠릅니다.

링크드 리스트의 삭제

새로운 데이터를 추가할 때는 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경해주고, 새로운 요소가 그 다음 요소를 참조하도록 변경하기만 하면 되므로 처리속도가 매우 빠릅니다.

링크드 리스트의 삽입

 

Doubly LinkedList(이중 연결리스트)

LinkedList는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전 요소에 대한 접근은 어렵다는 단점이 있습니다. 이 점을 보완하기 위해 나온 것이 Doubly LinkedList(이중 연결 리스트)입니다. 

Doubly LinkedList(이중 연결 리스트)는 단순히 LinkedList에 참조변수를 하나 더 추가하여 다음 요소에 대한 참조뿐 아니라 이전 요소에 대한 참조가 가능하도록 했을 뿐, 그 외에는 LinkedList와 동일합니다. 

Doubly LinkedList(이중 연결리스트)는 LinkedList보다 각 요소에 대한 접근과 이동이 쉽기 때문에 LinkedList보다 더 많이 사용됩니다.

Doubly LinkedList(이중 연결리스트)

 

Doubly Circular LinkedList(이중 원형 리스트)

Doubly LinkedList(이중 연결 리스트)의 접근성을 보다 향상시킨 것이 Doubly Circular LinkedList(이중 원형 리스트)인데 단순히 Doubly LinkedList(이중 연결리스트)의 첫 번째 요소와 마지막 요소를 서로 연결시킨 것입니다. 이렇게 하면, 마지막 요소의 다음 요소가 첫 번째 요소가 되고, 첫 번째 요소의 이전 요소가 마지막 요소가 됩니다.

Doubly Circular LinkedList(이중 원형 리스트)

 

사실 Java에서 LinkedList 클래스는 이름과 달리 LinkedList가 아닌 Doubly LinkedList(이중 연결 리스트)로 구현되어 있습니다. 이는  LinkedList의 단점인 낮은 접근성(accessability)을 높이기 위해서입니다.

 

ArrayList와 LinkedList의 성능 차이

실제로 아래 코드를 통해 ArrayList와 LinkedList에서의 추가와 삭제 연산의 차이를 알아볼 수 있습니다.

import java.util.*;

public class Test {
    public static void main(String args[]) {
        // 추가할 데이터의 개수를 고려하여 충분히 잡아야한다.
        ArrayList al = new ArrayList(2000000);
        LinkedList ll = new LinkedList();

        System.out.println("= 순차적으로 추가하기 =");
        System.out.println("ArrayList :" + add1(al));
        System.out.println("LinkedList :" + add1(ll));
        System.out.println();
        System.out.println("= 중간에 추가하기 =");
        System.out.println("ArrayList :" + add2(al));
        System.out.println("LinkedList :" + add2(ll));
        System.out.println();
        System.out.println("= 중간에서 삭제하기 =");
        System.out.println("ArrayList :" + remove2(al));
        System.out.println("LinkedList :" + remove2(ll));
        System.out.println();
        System.out.println("= 순차적으로 삭제하기 =");
        System.out.println("ArrayList :" + remove1(al));
        System.out.println("LinkedList :" + remove1(ll));
    }

    public static long add1(List list) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) list.add(i + "");
        long end = System.currentTimeMillis();
        return end - start;
    }

    public static long add2(List list) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) list.add(500, "X");
        long end = System.currentTimeMillis();
        return end - start;
    }

    public static long remove1(List list) {
        long start = System.currentTimeMillis();
        for (int i = list.size() - 1; i >= 0; i--) list.remove(i);
        long end = System.currentTimeMillis();
        return end - start;
    }

    public static long remove2(List list) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) list.remove(i);
        long end = System.currentTimeMillis();
        return end - start;
    }
}

실행환경에 따라 결과는 조금 다르겠지만 제가 돌렸을 때의 결과는 아래와 같습니다.

실행 결과

 

결론

• 순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠르다.
• 중간 데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다.