Array vs LinkedList — 면접에서 진짜 묻는 것

"Array는 O(1) 접근, LinkedList는 O(1) 삽입" — 이 한 줄 공식의 이면에는 메모리 구조와 CPU 캐시라는 근본적인 차이가 숨어 있습니다.

"Array와 LinkedList의 차이점"은 자료구조의 가장 기본적인 질문입니다. 하지만 시간 복잡도 표만 외우면 "왜 그런 복잡도가 나오는지", "실무에서 정말 그렇게 동작하는지"를 설명할 수 없습니다.

개념 정의

Array 는 동일한 크기의 요소를 연속된 메모리 공간 에 저장하는 자료구조입니다. LinkedList 는 각 노드가 데이터와 다음 노드의 주소(포인터)를 가지며, 메모리상에 불연속적으로 분포하는 자료구조입니다.

Array의 동작 원리

메모리 구조

Array를 선언하면 메모리에 연속된 블록이 할당되고, 각 요소가 같은 크기로 나란히 들어갑니다.

메모리 주소:  [100] [104] [108] [112] [116]
Array 값:      10    20    30    40    50
인덱스:         0     1     2     3     4

인덱스 접근이 O(1)인 이유

int가 4바이트라면, 시작 주소가 100일 때 array[3]의 주소는 100 + (3 x 4) = 112입니다. 이 산술 연산은 요소가 몇 개든 ** 덧셈과 곱셈 한 번 **이면 됩니다. 배열이 연속된 메모리에 동일 크기 요소를 저장하기 때문에, 이 주소 계산 공식이 성립합니다.

Array의 O(1) 접근은 "연속 메모리 + 동일 크기 요소"라는 두 가지 전제에서 나옵니다. 이 전제가 깨지면 (예: 가변 길이 요소) O(1) 접근은 불가능합니다.

삽입/삭제가 O(n)인 이유

연속 메모리라는 강점이 삽입/삭제에서는 약점이 됩니다. 중간에 요소를 넣으려면 그 뒤의 모든 요소를 한 칸씩 밀어야 하기 때문입니다.

[10, 20, 30, 40, 50]에서 인덱스 2에 25를 삽입:

1. 30, 40, 50을 한 칸씩 뒤로 밀기  → O(n)
2. 인덱스 2에 25 넣기              → O(1)

결과: [10, 20, 25, 30, 40, 50]

맨 앞에 삽입하면 전체 요소를 이동해야 하므로 최악의 경우 O(n)입니다.

LinkedList의 동작 원리

메모리 구조

LinkedList는 각 ** 노드 **가 데이터와 포인터를 가지고, 메모리 어디에든 흩어져 있을 수 있습니다.

노드1 [data: 10, next: →] → 노드2 [data: 20, next: →] → 노드3 [data: 30, next: null]

메모리 주소: 200           504           320
(연속되지 않음)

인덱스 접근이 O(n)인 이유

노드가 메모리에 불연속적으로 흩어져 있으므로, 주소를 산술 연산으로 계산할 수 없습니다. 3번째 요소를 찾으려면 head부터 시작해서 next 포인터를 3번 따라가야 합니다. n번째 요소를 찾으려면 n번 이동해야 하므로 O(n)입니다.

삽입/삭제가 O(1)인 조건

삽입 위치의 노드 참조를 이미 알고 있다면, 포인터만 변경하면 됩니다.

노드1 → 노드2 → 노드3

노드2 뒤에 새 노드를 넣으려면:
1. 새 노드의 next = 노드3    → O(1)
2. 노드2의 next = 새 노드    → O(1)

결과: 노드1 → 노드2 → 새 노드 → 노드3

다른 노드를 이동시킬 필요가 없습니다. 하지만 ** 삽입 위치를 찾는 탐색 자체가 O(n)**이므로, "LinkedList의 삽입은 O(1)"이라는 말은 위치를 이미 알고 있을 때만 성립합니다.

CPU 캐시와 실제 성능

시간 복잡도만 놓고 보면 "읽기는 Array, 삽입/삭제는 LinkedList"로 정리됩니다. 하지만 실제 성능에는 CPU 캐시 라는 변수가 있습니다.

1. Array는 메모리가 연속되어 있어서, 한 요소를 읽으면 인접 요소들이 캐시 라인에 같이 올라옵니다(spatial locality).
2. 이 때문에 순차 접근 시 캐시 적중률이 높아 실제 속도가 빠릅니다.
3. LinkedList는 노드가 메모리에 흩어져 있어서 캐시 미스가 빈번하게 발생합니다.
4. 결과적으로, 이론적으로 LinkedList가 유리한 삽입/삭제도 **캐시 효과를 고려하면 ArrayList가 더 빠른 경우가 많습니다 **.

Java 공식 문서에서도 대부분의 경우 ArrayList를 권장합니다. LinkedList가 유리한 경우는 "리스트 앞쪽에서 빈번하게 삽입/삭제하면서 순차 접근은 거의 하지 않는" 매우 제한적인 상황뿐입니다.

ArrayList의 동적 확장

Java의 ArrayList는 내부적으로 ** 배열 **을 사용하되, 용량이 부족하면 자동으로 확장합니다. 초기 용량(default 10)으로 배열을 생성하고, 요소가 가득 차면 1.5배 크기의 새 배열 을 만들어 복사합니다.

// ArrayList의 내부 동작 (의사 코드)
Object[] elementData = new Object[10];
int size = 0;

public void add(Object e) {
    if (size == elementData.length) {
        int newCapacity = elementData.length + (elementData.length >> 1); // 1.5배
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    elementData[size++] = e;
}

확장 시 기존 배열을 통째로 복사하므로 O(n)이 걸립니다. 하지만 확장은 매번 발생하지 않습니다. n번의 add() 중 배열 복사는 log(n)번 정도만 발생하고, 나머지는 단순 대입입니다. 총 비용을 n으로 나누면 상수에 수렴하므로, 분할 상환(amortized) O(1) 입니다.

주의할 점

LinkedList의 O(1) 삽입은 반쪽짜리

"LinkedList는 삽입이 O(1)"이라는 설명을 그대로 받아들이면 위험합니다. 포인터 변경 자체는 O(1)이지만, 삽입 위치를 찾는 탐색이 O(n)입니다. Java의 LinkedList.add(int index, E element)는 내부적으로 index까지 순회하므로 O(n)입니다.

ArrayList의 대량 삽입 시 초기 용량 미지정

대량 데이터를 넣을 것을 알면서 초기 용량을 지정하지 않으면, 리사이징이 반복됩니다. 10 -> 15 -> 22 -> 33 -> ... 로 확장될 때마다 전체 복사가 발생합니다.

// 10,000개를 넣을 예정이라면 초기 용량 지정
List<String> list = new ArrayList<>(10_000);

Array와 ArrayList 혼동

Java에서 "배열"이라고 할 때 고정 크기 Array를 말하는지, 동적 ArrayList를 말하는지 구분이 필요합니다. 두 가지는 내부 구조는 같지만(연속 메모리 배열) 확장 가능 여부와 API가 다릅니다.

정리