ArrayList vs LinkedList: Big-O는 맞는데, 왜 대부분 ArrayList가 더 빠를까?

Java 컬렉션을 처음 배울 때 보통 이렇게 외웁니다.

• ArrayList.get(i)는 O(1)
• LinkedList는 중간 삽입/삭제가 O(1)

그래서 직감적으로는 “삽입/삭제가 많으면 LinkedList가 유리하겠네”라고 생각하기 쉽습니다. 그런데 실제 서비스 코드나 벤치마크에서는 대체로 반대 결과가 자주 나옵니다.

이번 글에서는 그 이유를 Big-O가 아니라 CPU 캐시와 메모리 레이아웃 관점에서 정리해보겠습니다.

이 글에서 말하는 “메모리 모델”은 JMM(Java Memory Model: happens-before, visibility)이 아니라, CPU cache hierarchy + locality 일반론에 가깝습니다.

1) Big-O는 틀린 게 아니라, 생략이 많다

Big-O는 연산 횟수의 증가율을 설명합니다. 하지만 실제 실행 시간은 여기에 다음 요소가 함께 붙습니다.

• 메모리 접근 패턴(연속/불연속)
• 캐시 미스와 TLB 미스
• 분기 예측 실패
• 객체 할당/GC 비용

즉, 현실 성능은 대략 아래처럼 결정됩니다.

실행 시간 = 알고리즘 복잡도 + 메모리 계층 비용 + 런타임/JIT/GC 비용

그래서 복잡도 표만 보면 비슷해 보이는 연산이 실제로는 크게 벌어질 수 있습니다.

2) ArrayList와 LinkedList의 핵심 차이: 레이아웃

ArrayList의 OpenJDK 구현은 내부 버퍼 필드로 transient Object[] elementData를 사용합니다.¹ 반면 LinkedList의 OpenJDK 구현은 Node<E> first/last와 Node<E> { item, next, prev }를 유지하는 이중 연결 구조입니다.²

여기서 Object[]라고 쓰는 이유는 “런타임에서 제네릭 타입 매개변수가 지워진다(type erasure)“는 규칙과 맞닿아 있습니다.³⁴

ArrayList (contiguous references)
[ref][ref][ref][ref][ref]...

LinkedList (pointer chain)
Node <-> Node <-> Node <-> Node ...

여기서 중요한 포인트가 하나 있습니다.

• ArrayList가 locality 이점을 주는 대상은 “객체 자체”가 아니라 우선 “참조 배열(Object[])“입니다.
• 즉 원소가 참조하는 객체까지 항상 인접하다는 뜻은 아닙니다.

그럼에도 순회/인덱스 접근에서 유리한 이유는, 참조 배열 자체가 연속 메모리이기 때문입니다.

3) 왜 캐시가 승부를 바꾸는가

CPU는 메모리를 바이트 단위가 아니라 cache line 단위로 가져옵니다(많은 x86_64 환경에서 64B, 아키텍처별 차이 있음).⁵

배열은 연속 메모리라서, arr[i]를 읽을 때 주변 원소 참조들도 같이 캐시에 올라옵니다. 그래서 다음 접근이 캐시 히트가 될 가능성이 큽니다(공간 지역성).

반대로 linked list는 다음 노드 주소를 따라가야 하므로,

• 다음 데이터 위치를 미리 예측하기 어렵고
• pointer chasing으로 캐시/TLB 미스가 누적되기 쉽고
• 하드웨어 prefetcher가 잘 먹히지 않는 경우가 많습니다

Oracle dev.java의 공식 비교 자료도 ArrayList/LinkedList 선택 시 성능 관점을 함께 설명합니다.⁶

4) “LinkedList 삽입 O(1)“의 실무 함정

“LinkedList 삽입 O(1)“은 맞는 말입니다. 단, 삽입 위치의 노드를 이미 알고 있을 때에 한해서입니다.

대부분의 비즈니스 코드는 add(index, value) 또는 get(index) 형태를 사용합니다. 이 경우 먼저 해당 위치까지 탐색(O(n))이 필요하고, 여기서 pointer chasing 비용이 더해집니다.

결국 실무에서는 아래 패턴이 자주 나타납니다.

• 이론: 삽입 자체는 O(1)
• 현실: 위치 탐색 O(n) + 캐시 미스 + 노드 할당 비용

그래서 일반적인 List 사용에서는 ArrayList가 더 빠른 경우가 훨씬 많습니다.

5) Java 2D 배열: “완전 flat”이 아니라 array-of-arrays

여기서 자주 헷갈리는 포인트가 있습니다.

Java의 int[][]는 C 스타일의 단일 연속 2D 블록이 아니라, 배열 변수의 배열입니다.⁷

그래도 아래 순회는 성능 차이가 납니다.

// row-wise (보통 유리)
for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
        sum += a[i][j];
    }
}

// column-wise (보통 불리)
for (int j = 0; j < cols; j++) {
    for (int i = 0; i < rows; i++) {
        sum += a[i][j];
    }
}

이유는 간단합니다.

• row-wise: 같은 a[i] 내부를 연속 접근(좋은 locality)
• column-wise: 서로 다른 행 배열을 계속 점프(나쁜 locality)

즉 Java 2D 배열은 “완전 flat”이라서가 아니라, 행 내부 연속성 때문에 row-wise가 일반적으로 유리합니다.

6) Deque는 보통 ArrayDeque를 기본값으로

Deque/Queue/Stack 용도로는 LinkedList보다 ArrayDeque가 기본 선택에 가깝습니다.

Javadoc도 직접 이렇게 말합니다.

“ArrayDeque는 queue로 사용할 때 LinkedList보다 더 빠를 가능성이 높다.”⁸

물론 예외는 있습니다.

• null 원소를 꼭 저장해야 한다 (ArrayDeque는 null 금지)
• List API까지 함께 필요하다 (LinkedList는 List도 구현)

이런 요구가 없다면 Deque는 ArrayDeque를 먼저 고려하는 것이 보통 더 안전합니다.

7) 왜 지금 더 차이가 커졌나: memory wall

제가 이 주제를 “요즘 CPU에서 더 중요해졌다”고 보는 이유는, 알고리즘 교과서가 틀려서가 아니라 하드웨어 밸런스가 바뀌었기 때문입니다.

Wulf/McKee가 정리한 고전적인 memory wall 논점은 단순합니다. CPU 성능 향상 속도가 DRAM 지연 개선 속도보다 더 빨라서, 메모리 접근의 상대 비용이 시간이 갈수록 커진다는 점입니다.⁹

실무적으로는 “캐시 미스 한 번이 몇 ns인가”보다, **“코어가 그동안 몇 cycle을 놀게 되느냐”**가 더 중요합니다. McCalpin은 이미 1990년대 중반에 “cache miss 한 번 처리하는 동안 최신 프로세서는 100개 이상의 부동소수점 연산을 수행할 수 있다”고 정리했고, 지연(latency) 지배가 강해지는 방향을 지적했습니다.¹⁰

그래서 제 해석은 이렇습니다.

• pointer chasing이 과거에 없던 문제가 된 게 아니라
• 예전보다 miss penalty(특히 cycle 기준)가 더 커져서
• locality 차이가 실제 벽시계 시간에 더 크게 번역되기 쉬워졌습니다.

즉 “옛날엔 LinkedList도 충분히 빨랐다”는 단정은 조심해야 하지만, “현대 CPU에서는 locality를 놓치면 비용이 더 빠르게 커진다”는 방향은 역사적으로도 일관된 설명입니다.

8) 실무 선택 가이드

제가 실제 코드 리뷰에서 자주 쓰는 기준은 아래입니다.

1. 특별한 이유가 없으면 List는 ArrayList부터 시작
2. Deque가 필요하면 ArrayDeque부터 시작
3. LinkedList를 선택할 때는 “왜 LinkedList여야 하는지”를 코드 코멘트/리뷰에 남김

Big-O는 여전히 중요합니다. 다만 현대 CPU에서 데이터가 어떻게 배치되고 이동하는지까지 같이 봐야, 실제 서비스 성능을 예측할 수 있습니다.

9) 벤치마크

이제 실제로 얼마나 차이가 나는지, 어떤 상황에서 ArrayList가 우세하고 LinkedList가 우세한지를 직접 알아보도록 합시다.

• 예제 경로(canonical): examples/blog/2026-02-25-arraylist-vs-linkedlist-cache-locality
• GitHub 링크: https://github.com/Clickin/Clickin.github.io/tree/main/examples/blog/2026-02-25-arraylist-vs-linkedlist-cache-locality
• 벤치마크 코드: examples/blog/2026-02-25-arraylist-vs-linkedlist-cache-locality/src/main/java/io/clickin/bench/ListAndDequeBenchmark.java
• 실행 스크립트: examples/blog/2026-02-25-arraylist-vs-linkedlist-cache-locality/run-local-jmh.sh

아래는 제 로컬 기기에서 수행한 벤치마크 결과입니다.

• 설정: run-local-jmh.ps1 (full preset)
• JMH: warmup 5회(300ms), measurement 8회(300ms), fork 1, JVM args -Xms1g -Xmx1g
• Java: OpenJDK Temurin 25.0.1+8 LTS (results/java-version.txt)
• 머신: 13th Gen Intel Core i5-13600K, 14C/20T, MaxClock 3.5GHz (results/lscpu.txt)

아래는 같은 머신에서 findByValue(first/middle/last)를 full preset으로 포함해 측정한 결과입니다.

핵심은 first에서는 차이가 작지만, 탐색 길이가 길어질수록(middle, last) pointer chasing 비용이 누적되면서 LinkedList가 더 불리해진다는 점입니다.

메모리 할당량도 같이 비교하기 위해, arrayListBuildFromPayload vs linkedListBuildFromPayload를 -prof gc로 추가 측정했습니다.

즉 이 케이스에서는 LinkedList가 실행시간뿐 아니라, 노드 객체 생성 비용 때문에 메모리 할당량에서도 명확히 불리했습니다.

관찰 포인트는 세 가지입니다.

1. getMiddle처럼 임의 접근 성격이 강한 연산은 Array 계열(ArrayList)이 압도적으로 유리합니다.
2. head insert/remove, iterator remove처럼 노드 재연결이 핵심인 연산은 LinkedList가 매우 크게 앞섭니다.
3. deque offer/poll 시나리오에서는 ArrayDeque가 LinkedList보다 꾸준히 빠른 기본값으로 관측됩니다.

10) 정리

결론은 단순합니다.

• 이론 복잡도만 보면 LinkedList가 좋아보일 수 있지만 일반적인 Java 애플리케이션의 대부분 시나리오에서는 ArrayList(그리고 Deque라면 ArrayDeque)를 사용합시다.