같은 "순서 있는 목록"이지만 메모리에 놓이는 방식이 달라 성능 특성이 정반대다.
메모리에 어떻게 놓이나
배열 — 연속된 공간
주소: 1000 1004 1008 1012
[ 10 ][ 20 ][ 30 ][ 40 ]
→ i번째 주소 = 시작주소 + i × 4 ← 계산 한 번으로 바로 접근
링크드리스트 — 흩어진 노드가 포인터로 연결
[10|→] ─────► [20|→] ──► [30|→] ──► [40|null]
주소 3000 주소 8200 주소 1500 주소 9900
→ i번째를 찾으려면 처음부터 i번 따라가야 한다
이 그림 하나로 모든 차이가 설명된다.
시간복잡도
| 연산 | 배열 | 링크드리스트 |
|---|---|---|
| 인덱스 접근 | O(1) | O(n) |
| 맨 앞 삽입/삭제 | O(n) (전부 밀기) | O(1) |
| 중간 삽입/삭제 | O(n) | 노드를 이미 알면 O(1), 찾는 것 포함하면 O(n) |
| 맨 뒤 추가 | 분할 상환 O(1) | O(1) (tail 포인터 있으면) |
| 검색 | O(n) | O(n) |
표가 말해 주지 않는 것 — 실측은 배열이 거의 항상 이긴다
이론상 링크드리스트가 유리해 보이는 중간 삽입조차 현실에서는 배열이 빠른 경우가 많다. 이유는 캐시다.
CPU는 메모리에서 값 하나를 읽을 때 실제로는 64바이트(캐시 라인)를 통째로 가져온다
배열: [10][20][30][40] ← 한 번 읽으면 이웃까지 캐시에 올라옴
- 다음 원소 접근이 캐시 히트 (약 1ns)
링크드리스트: 노드가 여기저기 흩어져 있어
- 다음 노드는 거의 항상 캐시 미스 (약 100ns)
100배 차이다. 게다가 링크드리스트는 노드마다 포인터(8~16바이트)를 추가로 쓰므로 메모리도 더 먹는다.
자바
LinkedList는 사실상 쓰지 말라는 것이 통념이다. 실제로ArrayDeque가 큐·스택 용도로 모든 면에서 낫다.
그럼 링크드리스트는 언제 쓰나
- 노드 참조를 이미 들고 있고 그 자리에서 제거해야 할 때 → LRU 캐시의 이중 연결 리스트
- 리스트를 쪼개고 합치는 연산이 잦을 때
- 메모리가 조각나 큰 연속 공간을 확보할 수 없을 때
- 커널·임베디드처럼 동적 배열 재할당을 피해야 할 때
LRU 캐시가 대표 사례다. 해시맵이 노드 주소를 들고 있으므로 "찾는 데 O(n)"이라는 약점이 사라지고, O(1) 제거만 남는다.
면접 답변 골격
"복잡도만 보면 삽입·삭제는 링크드리스트가 유리하지만, 실제로는 캐시 지역성 때문에 배열이 대부분 빠릅니다. 링크드리스트는 노드 참조를 이미 갖고 있는 경우— LRU 캐시처럼—에 의미가 있습니다."