[Java] LinkedList, ArrayList를 구현하는 방식과 이에 따른 성능 비교해보기

0. 들어가면서

LinkedList, ArrayList는 자바 List<E> 인터페이스를 구현한 클래스들입니다. 그리고 List<E> 인터페이스는 Collection<E>를 구현하고 있고, Collection<E>는 최상위의 Iterable<T>을 구현하고 있습니다.

 

이러한 계층 구조의 상속과 분리는 특정 클래스들의 공통점과 차이점으로 인한 결과라고 볼 수 있는데요.

 

이번 시간에 살펴볼 ArrayList, LinkedList 역시 List<E>를 구현한 클래스들로 보면 공통점이 있지만, 서로 분리된 클래스라는 점에서는 분명 차이점이 존재하는 클래스들입니다.

 

그래서 이번 포스팅에서는 ArrayList와 LinkedList에 대해 정리해보고 각각의 클래스가 어떤 상황에서 사용하기 적합한지 직접 성능을 테스트해보려고 합니다.

 

 

1. ArrayList

ArrayList는 크기가 가변적으로 변하는 선형리스트입니다.

 

일반적인 배열과 같은 순차리스트이며 인덱스로 내부의 객체를 관리하는 점이 배열과 동일하지만, 배열은 한 번 선언하면 그 크기를 변경할 수 없는데 반하여 ArrayList는 크기를 가변적으로 변화시킬 수 있다는 점에서 차이를 가집니다.

 

ArrayList의 크기가 어떻게 변하는지 코드를 하나씩 들여다보겠습니다.

ArrayList의 기본 Capacity

자바에서 구현한 ArrayList<E> 클래스를 보면, 초기 리스트의 Capacity는 10으로 설정된 것을 볼 수 있습니다. ArrayList는 데이터를 삽입하면서 계속해서 사이즈를 확인하고, 아래와 같이 현재 리스트의 Capacity와 size를 비교하고 있습니다.

add()

Capacity, size를 확인하고 grow() 함수 호출

위의 ensureExplicitCapacity() 메서드를 보면, minCapacity와 elementData.length가 있습니다.

 

여기서 minCapacity가 현재 ArrayList에 실제 들어있는 데이터의 개수(size)이며, elementData.length가 허용 가능한 Capacity를 의미하는데요.

 

따라서, minCapacity - elementData.length > 0 조건이 성립하면 리스트의 사이즈를 늘려주는 작업 grow() 메서드를 호출하게 됩니다.

grow()

grow() 메서드는 기존의 Capacity(oldCapacity) 값과 그 값을 2로 나눈 값을 더해서 만듭니다. 약 1.5배를 만드는 것이죠. 그리고 마지막으로는 기존의 리스트에 있던 데이터를 새롭게 만든 리스트에 copy하는 과정을 거치게 됩니다. 

 

따라서 ArrayList는 인덱스를 기반으로 하기 때문에 탐색에 대한 속도는 분명 빠르겠지만, 삽입과 같은 연산에서는 리스트의 사이즈를 늘리려주고 원소들을 복사하는 등의 시간으로 인해 그다지 효율적이지 않다는 것을 예측해볼 수 있습니다.

 

 

2. LinkedList

연결 리스트(LinkedList)는 각 노드가 자신의 데이터와 포인터를 가지고 체인 형태로 연결된 자료구조입니다.

 

LinkedList를 구현하는 데는 Singly-LinkedList와 Doubly-LinkedList가 존재하는데요. 자바에서 기본적으로 제공하는 LinkedList는 Doubly LinkedList 구조를 기반으로 하여 각 노드의 포인터는 자신의 앞과 뒤 노드를 포인팅하고 있습니다.

 

LinkedList 클래스에서 중간에 어떤 노드를 삽입하기 위한 add() 메서드를 살펴보면 해당 클래스가 Doubly LinkedList로 구현되어 있음을 알 수 있는데요.

 

아래와 같이 중간에 데이터를 삽입하면, linkBefore() 메서드가 호출되고 linkBefore() 메서드를 보면 삽입하는 노드의 앞, 뒤 노드의 포인터를 변경해주는 작업을 하고 있음을 볼 수 있습니다.

LinkedList에서 삽입

 

정리하자면, LinkedList는 데이터를 담고 있는 노드들이 연결되어 있고 노드의 포인터는 이전 노드와 다음 노드를 연결하고 있기 때문에 LinkedList에 데이터를 추가하거나 삭제하면 앞뒤를 연결하면 포인터만 변경되고 나머지는 변경되지 않습니다.

 

따라서 중간에 데이터를 추가하거나 삭제하더라도, 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없기 때문에 ArrayList에 비해 데이터의 추가나 삭제가 용이합니다.

 

하지만 이를 반대로 생각하면 인덱스 기반의 자료구조가 아니기 때문에 데이터를 조회할 때는 순차적인 탐색을 필요로 하기 때문에 O(n) 시간의 시간 복잡도를 가지게 되죠.

 

결국 LinkedList는 단순한 데이터의 추가, 삭제가 많은 경우에 유용하게 사용할 수 있는 자료구조이며 만약 데이터의 조회나 정렬을 위한 자료구조를 생각한다면 ArrayList를 쓰는게 더 나은 선택이 됩니다.

 

그리고 이 말을 조금 더 곱씹어 생각해보면, 중간의 원소를 삽입하거나 삭제하는 연산을 할 때도 LinkedList의 성능이 좋지 않을 것을 예상할 수 있는데요. LinkedList는 해당 원소의 자리를 찾아가는 데 순차적인 탐색이 필요하기 때문입니다.

 

 

3. ArrayList, LinkedList에서의 조회와 삽입 성능 비교

[1] 원소 조회 성능 비교

10,000,000개의 원소를 삽입한 후에 999999번째 데이터를 조회하는 시간을 측정해보겠습니다.

결과

예상대로 LinkedList에서는 순차 탐색으로 인해 원소를 조회하는 시간이 더 오래 걸림을 알 수 있습니다.

 

 

[2] 10,000,000개의 원소 삽입 성능 비교

public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList<Integer> myLinkedList = new LinkedList<>();
        ArrayList<Integer> myArrayList = new ArrayList<>();


        long beforeTime = System.currentTimeMillis();
        addElement(myArrayList);
        long afterTime = System.currentTimeMillis();
        long diffTime = afterTime - beforeTime;
        System.out.println("ArrayList 삽입 시간: " + diffTime + "ms");

        beforeTime = System.currentTimeMillis();
        addElement(myLinkedList);
        afterTime = System.currentTimeMillis();
        diffTime = afterTime - beforeTime;
        System.out.println("LinkedList 삽입 시간: " + diffTime + "ms");
    }

    public static void addElement(List list){
        for(int i = 0; i < 10000000; i++){
            list.add(i);
        }
    }
}

결과

결과를 보면 위에서 설명한 것처럼 대량의 원소를 삽입할 때 ArrayList의 삽입 시간이 LinkedList에 비해 훨씬 오래 걸리는 것을 알 수 있습니다.

 

 

[3] 중간에 원소를 삽입할 때 성능 비교

이번에는 천 만개의 원소를 넣어놓은 상태에서 중간에 원소 하나를 삽입해보겠습니다.

결과

예상대로 LinkedList에서 원소를 삽입하는 데 더 오랜 시간이 걸렸습니다.

 

 

4. 정리

ArrayList, LinkedList 비교

 

위 표는 지금까지 설명한 ArrayList와 LinkedList의 연산 속도 차이를 정리해서 보여줍니다.

 

각 클래스의 성격과 동작 원리를 이해한다면 위 표를 외우지 않아도 자연스럽게 이해할 수 있을 것 같습니다.

 

감사합니다.