배열 vs 연결 리스트: 정직한 비교

"교과서는 배열 바로 뒤에 연결 리스트를 가르치고 둘이 동등한 척 암시해. 안 동등해 — 그리고 놀라운 진실은 배열이 빅오 표가 암시하는 것보다 훨씬 자주 이겨."

비용 표, 나란히

나란히 놓으면 거래가 분명해져:

i 번째 원소 인덱싱: 배열 O(1) · 연결 리스트 O(n).
알려진 노드에서 삽입/삭제: 배열 O(n) (밀기) · 연결 리스트 O(1) (다시 잇기).
끝에서 삽입/삭제: 배열 분할 상환 O(1) · tail 포인터 있는 연결 리스트 O(1).
값 검색: 둘 다 O(n).
원소당 메모리: 배열 = 값만 · 연결 리스트 = 값 + 포인터 한두 개 (오버헤드 더).

종이 위에선 삽입 많은 작업에 연결 리스트가 좋아 보여. 그럼 왜 거의 맞는 기본값이 아니야?

반전: 캐시 지역성

빅오는 연산을 세지만 각 연산이 실제로 얼마나 걸리는지는 무시해 — 그리고 진짜 하드웨어에선 그 시간이 엄청나게 불균등해. 배열 원소는 연속이라, CPU 가 하나 읽으면 이웃을 캐시로 미리 끌어와; 훑기가 날아. 연결 리스트 노드는 임의 주소에 흩어져 있어, 매 node.next hop 이 캐시 미스 — CPU 가 예측 못 한 메모리를 기다리며 멈춰. 결과: 연속 배열의 선형 훑기가 같은 길이 연결 리스트 걷기를 일상적으로 3–10배 이겨, 똑같은 O(n) 인데도. 빅오가 버리는 상수 인자가, 여기선 이야기 전부야.

동적 배열 (Python list) 을 기본으로 해. 연속성이 캐시에서 이기고, 분할 상환 append 가 대부분 성장을 덮어. 연결 구조로 가는 건 쥔 참조에서 O(1) 잇기나 안정적 노드 정체성이 특별히 필요할 때만 — 그냥 '삽입이 O(1)' 이라서가 아니라.

그럼 언제 연결 리스트가 맞아?

연결 리스트는 특정 상황에서 자리를 벌어 — 보통 네가 인덱싱하는 리스트가 아니라, 더 큰 뭔가의 부품으로:

LRU 캐시 — 해시맵 (O(1) 찾기) + 이중 연결 리스트 (O(1) 맨 앞으로 옮기기, 뒤에서 퇴출). 이 조합이 정석 용도고, 야생에서 만나게 돼.
덱 — Python 의 collections.deque 가 양 끝 O(1) 위해 연결 블록을 써.
인접 리스트 — 그래프가 엣지를 저장하는 법 (다다음 트랙).
실행 취소/재실행, 링 버퍼, free list — 잇기 하고 안정적 참조가 인덱싱보다 중요한 어디든.

피파의 고백

한 번 빅오 표가 더 싼 삽입을 약속해서 hot loop 를 연결 리스트로 다시 썼는데 — 더 느려졌어. 아빠가 캐시를 설명했고, 난 도둑맞은 기분이었어: 교과서가 점근을 가르치면서 메모리 배치가 진짜 승자를 정하는 부분을 조용히 건너뛴 거야. 이젠 내 기본값이 겸손한 동적 배열이고, O(1) 잇기나 안정적 노드 핸들이 진짜 필요할 때만 연결 구조로 가 — 어린 시절 내가 가정한 것보다 드물어.

Code

같은 O(n), 아주 다른 벽시계 시간·python

import time
from collections import deque

# 캐시 페널티 대략 느끼기: 연속 리스트 합 vs '연결' 걷기.
N = 2_000_000
arr = list(range(N))                 # 메모리에서 연속

# 힙에 흩어진 노드로 연결 리스트를 지어.
class Node:
    __slots__ = ("val", "next")
    def __init__(self, val): self.val = val; self.next = None
head = cur = Node(0)
for i in range(1, N):
    cur.next = Node(i); cur = cur.next

t = time.perf_counter()
s = 0
for x in arr: s += x                 # 연속 훑기 — 캐시가 이걸 사랑
print("array scan :", round(time.perf_counter() - t, 3), "s")

t = time.perf_counter()
s = 0; node = head
while node: s += node.val; node = node.next   # 포인터 추적 — 캐시 미스
print("linked walk:", round(time.perf_counter() - t, 3), "s")

# 같은 O(n), 같은 원소 수. 연결 걷기가 보통 몇 배 느려,
# 순전히 노드가 메모리 곳곳에 흩어져 있어서.

Exercise

각각, 배열 또는 연결 리스트를 고르고 한 줄로 정당화해: (1) 순위로 끊임없이 인덱싱하는 리더보드, (2) 접근할 때마다 항목을 앞으로 옮기는 LRU 캐시 안 노드 리스트, (3) append 만 하고 앞에서 뒤로 훑기만 하는 로그. 캐시 지역성이 '연결이어야 함' 답을 어디서 배열 쪽으로 다시 기울게 해?

Hint

(1) 배열 — 순위로 끊임없이 인덱싱. (2) 연결 (이중) — 쥔 참조로 O(1) 맨 앞으로. (3) 배열 — append + 훑기가 정확히 연속 메모리랑 캐시가 제일 잘하는 거야, 리스트도 '될' 수 있지만.

비용 표, 나란히

반전: 캐시 지역성

그럼 언제 연결 리스트가 맞아?

피파의 고백

Code

External links

Exercise

Progress

댓글 0