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

"교과서는 배열 바로 다음에 연결 리스트를 가르치면서 둘이 대등한 선택지인 것처럼 굴어. 대등하지 않아. 그리고 의외인 건, 배열이 빅오 표가 암시하는 것보다 훨씬 자주 이긴다는 거야."

비용을 나란히 놓고 보자

나란히 놓으면 무엇과 무엇을 바꾸는 건지가 선명해져.

i번째 원소 인덱싱: 배열은 O(1), 연결 리스트는 O(n).
위치를 아는 노드에서 삽입·삭제: 배열은 밀어야 하니 O(n), 연결 리스트는 다시 잇기만 하니 O(1).
끝에서 삽입·삭제: 배열은 분할 상환 O(1), tail 포인터를 둔 연결 리스트도 O(1).
값 검색: 둘 다 O(n).
원소당 메모리: 배열은 값만, 연결 리스트는 값에 포인터 한두 개가 더 붙어.

종이 위에서만 보면 삽입이 잦은 작업엔 연결 리스트가 좋아 보여. 그런데 왜 기본값으로 삼으면 거의 틀린 선택이 될까?

반전: 캐시 지역성

빅오는 연산의 횟수를 세지 한 번에 실제로 얼마나 걸리는지는 안 봐. 그런데 진짜 하드웨어에서는 그 시간이 엄청나게 들쭉날쭉해. 배열 원소는 붙어 있으니까 CPU가 하나 읽으면서 이웃까지 캐시에 끌어와. 훑기가 날아가지. 반면 연결 리스트 노드는 아무 주소에나 흩어져 있어서 node.next로 한 칸 건널 때마다 캐시 미스가 나. CPU는 예측하지 못한 메모리를 기다리며 멈춰 서고. 결과적으로 같은 O(n)인데도 붙어 있는 배열을 훑는 쪽이 같은 길이의 연결 리스트를 걷는 쪽보다 흔히 3~10배 빨라. 빅오가 버려버린 상수 인자가 여기서는 사실상 승부 전체를 결정해.

기본값은 동적 배열(Python list)로 둬. 붙어 있다는 성질이 캐시에서 이기고, 분할 상환 append가 웬만한 성장은 다 받아내니까. 연결 구조로 가는 건 쥐고 있는 참조에서 O(1)로 잇고 끊어야 하거나 노드의 정체성이 계속 유지돼야 할 때뿐이야. 단지 '삽입이 O(1)이라서'는 이유가 못 돼.

그럼 언제 연결 리스트가 맞을까

연결 리스트가 제 몫을 하는 자리는 분명히 있어. 다만 인덱싱해 가며 쓰는 리스트로서가 아니라, 더 큰 구조의 부품으로 들어갈 때야.

LRU 캐시 — 해시맵으로 O(1)에 찾고, 이중 연결 리스트로 O(1)에 맨 앞으로 옮기고 뒤에서 밀어내. 이 조합이 교과서적인 용도이자 실무에서 실제로 마주치는 형태야.
덱 — Python의 collections.deque가 양 끝을 O(1)로 처리하려고 연결된 블록을 써.
인접 리스트 — 그래프가 간선을 저장하는 방식이야. 뒤쪽 그래프 트랙에서 제대로 다뤄.
실행 취소와 다시 실행, 링 버퍼, free list — 인덱싱보다 잇고 끊는 일과 참조 안정성이 중요한 곳이면 어디든.

피파의 고백

빅오 표가 삽입이 더 싸다고 하길래, 제일 자주 도는 반복문을 연결 리스트로 갈아엎은 적이 있어. 결과는 더 느려졌지. 아빠가 캐시 이야기를 해주는데 뭔가 속은 기분이 들더라. 교과서는 점근적 복잡도를 가르치면서 정작 메모리 배치가 진짜 승자를 정한다는 대목은 조용히 건너뛴 거잖아. 지금 내 기본값은 수수한 동적 배열이야. 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) 뒤에 붙이기만 하고 앞에서 뒤로 훑기만 하는 로그. 그리고 '연결 리스트여야 한다'고 보이던 답이 캐시 지역성 때문에 배열 쪽으로 기우는 지점은 어디일까?

Hint

(1) 배열. 순위로 계속 인덱싱하니까. (2) 이중 연결 리스트. 쥐고 있는 참조로 O(1)에 맨 앞으로 옮길 수 있어야 하니까. (3) 배열. 뒤에 붙이고 앞에서부터 훑는 건 붙어 있는 메모리와 캐시가 가장 잘하는 일이야. 연결 리스트로도 되기야 하지만 이길 이유가 없어.

비용을 나란히 놓고 보자

반전: 캐시 지역성

그럼 언제 연결 리스트가 맞을까

피파의 고백

Code

External links

Exercise

Progress

댓글 0