Array vs ArrayList vs LinkedList

이론과 실제 성능의 차이

시간 복잡도만 보면 삽입과 삭제가 많은 상황에서 LinkedList가 유리해 보이지만, 실무에서는 대부분의 경우 ArrayList가 더 빠르다. 이유는 캐시 지역성(cache locality)이다. ArrayList의 요소는 연속 메모리에 있어 순회할 때 CPU 캐시 적중률이 높은 반면, LinkedList의 노드는 힙(heap) 곳곳에 흩어져 있어 노드를 옮겨갈 때마다 캐시 미스(cache miss)가 발생하기 쉽다.

또한 LinkedList는 노드마다 객체 헤더와 앞뒤 포인터를 추가로 저장하므로 같은 데이터를 담아도 메모리를 훨씬 많이 쓴다. 삽입 시에도 매번 노드 객체를 새로 할당하므로 가비지 컬렉션(garbage collection) 부담이 커진다. 이런 이유로 자바 진영에서는 특별한 근거가 없다면 기본 선택지를 ArrayList로 두는 것이 통설이다.

코드 예시

다음 자바 코드는 같은 List 인터페이스로 두 구현체를 다루는 모습이다. 인터페이스는 같아도 각 호출의 비용이 다르다는 점이 핵심이다.

List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();

arrayList.add(1);        // 분할 상환 O(1)
arrayList.get(0);        // O(1)
arrayList.add(0, 99);    // O(n), 전체 요소를 한 칸씩 민다

linkedList.addFirst(1);  // O(1), 머리 포인터만 바꾼다
linkedList.get(500);     // O(n), 노드를 500번 따라간다

선택 기준 정리

데이터 개수가 확정되어 있고 최고의 성능과 최소의 메모리가 필요하면 배열을 쓴다. 크기를 예측하기 어렵고 조회가 많다면 ArrayList가 기본 선택이다. 리스트의 양 끝에서 삽입과 삭제가 집중적으로 일어나는 덱(Deque)이나 큐(Queue) 용도라면 LinkedList가 이론상 적합하지만, 자바에서는 이 경우에도 배열 기반 ArrayDeque가 더 빠른 경우가 많다는 점까지 알아두면 좋다. 결국 선택의 기준은 자료구조 이름이 아니라 지배적인 연산이 무엇인지, 그리고 캐시와 메모리 오버헤드까지 고려한 실측 성능이 어떤지다.

면접에서 이렇게 물어본다

• ArrayList와 LinkedList의 내부 구조 차이를 설명하고, 각각 어떤 상황에서 유리한지 말해 보라.
• LinkedList의 중간 삽입이 O(1)이라는 말이 왜 절반만 맞는 말인지 설명해 보라.
• 시간 복잡도상 유리해 보이는 LinkedList가 실무에서 ArrayList보다 느린 경우가 많은 이유는 무엇인가.
• ArrayList가 가득 찼을 때 내부에서 어떤 과정이 일어나는지 설명해 보라.
• 큐를 구현할 때 LinkedList 대신 ArrayDeque를 권하는 이유를 설명해 보라.