List 시간복잡도

지금부터 자바가 제공하는 자바 컬렉션 프레임워크의 리스트 시간 복잡도를 살펴보겠습니다. 
List를 대표하는 ArrayList와 LinkedList를 살펴보고, 빅오로 표현되는 시간 복잡도 말고도 실제 삽입과 삭제 속도도 측정해 비교해 보겠습니다.
 

List 시간 복잡도 (ArrayList, LinkedList)

연산	ArrayList	LinkedList
인덱스 끝에 삽입	O(1), 더블링 발생 시 O(n)	O(1)
인덱스 중간에 삽입	O(n)	탐색 O(n), 삽입 O(1)
인덱스 끝에서 삭제	O(1)	O(1)
인덱스 중간에서 삭제	O(n)	탐색 O(n), 삭제 O(1)
조회	O(1)	O(n)

 
ArrayList는 동적 배열이고, LinkedList는 연결 리스트로 구현되어 있기 때문에 위 표와 같이 같은 List 더라도 연산에 시간복잡도에 차이가 있습니다.
 

ArrayList (동적 배열)

ArrayList는 아래 그림과 같이 연속된 배열이면서 공간이 가득 찰 경우 더블링을 발생시켜 미리 넣을 데이터 양을 모른 상태로 사용할 수 있습니다.

ArrayList

 

ArrayList의 더블링 구조를 살펴봅시다. ArrayList는 초깃값으로 크기가 10인 배열을 설정하고, 값으로 공간이 다 차면 더블링으로 늘려줍니다. 이때 Growth Factor(성장 인자)라 불리는 재할당 비율은 2배가 아니라 1.5배입니다. 
즉 배열이 가득 차면 1.5배 더 큰 메모리 영역을 할당하고 다시 데이터를 모두 복사하는 식으로 동작합니다. 
 
동적 배열인 ArrayList의 인덱스 끝에 삽입하는 대부분의 경우는 O(1)이지만, 배열의 공간이 모두 찬 경우 더블링이 일어나며 O(n)이 됩니다. 하지만 분할 상황 분석에 따라 ArrayList의 인덱스 끝에 삽입하는 시간복잡도는 여전히 O(1)로 이해할 수 있습니다.

 

인덱스 끝에서의 삽입과 삭제는 모두 O(1)이지만, 인덱스 중간에 삽입하거나 삭제할 경우 ArrayList와 같은 동적 배열의 경우 연속된 배열 구조이기 때문에 신규 엘리먼트를 포함하여 전체를 새로운 공간에 복사해야 합니다. 따라서 인덱스 중간에 삽입 또는 삭제의 경우 O(n)이 소요됩니다.

 

동적 배열인 ArrayList의 가장 큰 장점은 어느 위치에 있든 인덱스를 지정하면 O(1)에 조회가 가능하다는 점입니다. 항상 지정한 순서대로 연속된 배열에 위치하므로 즉시 조회가 가능하다는 점이 배열의 가장 큰 장점입니다.
 

LinkedList (연결 리스트)

LinkedList는 포인터 기반의 연결 방식으로 노드끼리의 결합입니다. 여기서 노드는 데이터를 저장하는 부분과 다음 노드에 대한 포인터로 이루어져 있습니다. 그리고 첫 번째 노드를 Head, 마지막 노드를 Tail이라고 부릅니다. 아래 그림으로 살펴봅시다.

연결 리스트

 
연결 리스트인 LinkedList는 인덱스 끝에 삽입과 삭제의 경우 O(1)에 바로 가능합니다. 하지만 인덱스 중간에 삽입 또는 삭제를 할 경우 해당 위치까지 거슬러 내려가야 합니다. 배열과 달리 인덱스로 엘리먼트를 지정할 수 없기 때문에 삽입, 삭제 전에 해당 엘리먼트를 찾는 탐색이 필요합니다. 이때 탐색에는 O(n)이 소요됩니다. 하지만 삽입과 삭제 자체는 간단히 노드를 연결해 주거나 끊어주면 되기 때문에 O(1)이 소요됩니다. 
 
연결 리스트의 경우 조회할 때 위에서 보았듯이 연결 리스트 전체를 순회하며 O(n)이 소요됩니다. 따라서 조회가 잦다면 연결 리스트 구현인 LinkedList를 사용하는 것은 지양해야 합니다.
 

ArrayList와 LinkedList의 실제 엘리먼트 삽입, 삭제 속도

코딩 테스트나 실무에서 자료구조를 선택할 때 시간 복잡도도 중요하지만 실제로 얼마만큼의 속도로 동작하는지 알아야 어떤 자료구조를 사용할지 선택할 수 있습니다.
 
지금까지만 보면 ArrayList의 인덱스 끝에서 삽입과 삭제의 시간복잡도와 LinkedList의 인덱스 끝에서 삽입과 삭제의 시간복잡도가 O(1)로 같았습니다. 또한 ArrayList의 인덱스 중간에서 삽입과 삭제의 시간복잡도와 LinkedList에서 인덱스 중간에서 삽입과 삭제의 시간 복잡도가 O(n)로 같았습니다.
 
하지만 최악의 경우를 따지는 빅오가 아닌 실제 속도에도 차이가 없을까요? 빅오 계산에서는 n에 붙은 상수항을 무시하기 때문에 같은 빅오 일지라도 실제 속도에는 차이가 있을 수 있습니다. 지금부터 살펴봅시다.
 

엘리먼트 삽입

먼저 엘리먼트를 삽입하는 경우를 살펴봅시다.
ArrayList와 LinkedList 모두 엘리먼트를 삽입할 때 O(1)이 소요됩니다. 실제 속도를 살펴봅시다.

// ArrayList<Integer> 1억 개 삽입
List<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < 100000000; i++) 
    arrayList.add(1);
    
// LinkedList<Integer> 1억 개 삽입
List<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < 100000000; i++) 
    linkedList.add(1);

 
ArrayList는 배열 공간이 다 차면 더블링이 일어나면서 O(n)이 소요되기 때문에 1억 개의 엘리먼트를 삽입할 때 LinkedList 보다 ArrayList가 시간이 더 걸릴 거라 예상할 수 있습니다. 하지만 실제 결과는 LinkedList가 ArrayList 보다 훨씬 더 느립니다. 1억 개의 엘리먼트를 삽입한 결과는 아래와 같습니다.

• ArrayList<Integer> 1억 개 삽입 : 2265밀리초
• LinkedList<Integer> 1억 개 삽입 : 17231밀리초 

더블링이 일어나는 ArrayList 보다 LinkedList가 8배나 더 느린 이유는 LinkedList의 노드에 있습니다.
ArrayList와 같이 O(1)이지만, LinkedList의 경우 메모리를 엘리먼트를 삽입할 때 노드를 할당해야 하는 등의 훨씬 더 비싼 작업이 수행되기 때문에 실제 삽입 속도는 더 느릴 수밖에 없습니다.
시간 복잡도에서 생략된 상수 항이 LinkedList가 더 큰 사실을 알 수 있습니다.
 
ArrayList와 LinkedList의 자바 컬렉션 프레임워크 내구 구현을 살펴보면 아래와 같습니다.

// ArrayList.add()
public boolean add(E e) {
    ...
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

// LinkedList.add()
public boolean add(E e) {
    ...
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else 
        l.next = newNode;
    size++;
    modCount++;
}

 
ArrayList.add()의 경우 더블링이 필요한지 단순히 크기 비교만 한 뒤 바로 값을 삽입하지만, LinkedList.add()는 별도의 Node를 선언하고 연결하는 작업이 필요합니다. Node 선언과 같은 객체 생성은 매우 비싼 작업이기 때문에 시간 복잡도가 O(1)이라도 훨씬 더 오랜 시간이 걸리는 것입니다.
 
컴퓨터과학에서의 O(1)은 굉장히 이상적인 시간 복잡도겠지만, 코딩 테스트나 실무에서는 O(1)이라도 위의 LinkedList.add()와 같은 경우를 인지하고 있어야 합니다.
 

엘리먼트 삭제

이번에는 엘리먼트 삭제 속도를 살펴보겠습니다.
인덱스 중간에서 엘리먼트를 삭제하면 ArrayList나 LinkedList 모두 시간 복잡도 O(n)이 소요됩니다.
ArrayList는 삭제할 엘리먼트를 찾는 과정은 O(1)이지만, 연결된 배열로 해당 엘리먼트를 제외한 나머지를 다시 복사해야 해서 O(n)이 소요됩니다. 반면 LinkedList는 삭제할 엘리먼트를 찾는 과정에서 순회를 하며 O(n)이 소요되고 삭제에는 O(1)이 소요됩니다.
 
그렇다면 실제 엘리먼트 삭제 속도를 살펴보겠습니다.

// ArrayList<Integer> 1000000번째 인덱스 100개 삭제
for (int i = 0; i < 100; i++)
    arrayList.remove(1000000);

// LinkedList<Integer> 1000000번째 인덱스 100개 삭제
for (int i = 0; i < 100; i++)
    linkedList.remove(1000000);

 
 
결과는 아래와 같습니다.

• ArrayList<Integer> 1000000번째 인덱스 100개 삭제 : 9921밀리초
• LinkedList<Integer> 1000000번째 인덱스 100개 삭제 : 556밀리초

새로운 공간에 나머지 엘리먼트를 모두 복사하는 ArrayList는 꽤 비싼 작업을 O(n)으로 실행해야 하지만 LinkedList는 상대적으로 부담이 적은 탐색에만 O(n)을 소요하기 때문에 ArrayList 보다 LinkedList가 20배 가까이 빠른 것입니다.
 
정리하면 비슷한 시간 복잡도라도 ArrayList는 인덱스 끝에서 삽입과 조회가 빠르고, LinkedList는 인덱스 중간에서의 삽입과 삭제가 빠르다는 사실을 알 수 있었습니다.