컴퓨터공학 300 주제 시리즈의 042번째 글이다. 전체 지도는 여기.

한 줄 요약

연결 리스트는 원소마다 “다음 원소의 주소”를 함께 들고 다니는 구조라서, 위치만 알면 끼우고 빼는 일이 O(1) 이지만, i 번째를 찾으려면 처음부터 따라가야 하고 캐시도 잘 못 쓴다.

왜 필요한가

앞 글의 배열은 중간 삽입·삭제가 O(n) 이었다. 뒤쪽을 다 밀어야 하기 때문이다. 연결 리스트는 “원소들이 메모리에 붙어 있어야 한다”는 조건을 버려서 이 문제를 없앤다. 각 원소가 다음 원소를 가리키기만 하면 되니, 끼워 넣을 때는 포인터 두어 개만 바꾸면 된다.

다만 연결 리스트를 배우는 진짜 이유는 “배열 대신 쓰려고”가 아닌 경우가 많다. 포인터로 구조를 엮는 방법, 즉 노드와 링크라는 사고방식은 트리, 그래프, 해시 테이블의 체이닝, LRU 캐시까지 그대로 이어진다. 그리고 운영체제 커널처럼 객체가 여러 목록에 동시에 걸려 있어야 하는 곳에서는 지금도 핵심 도구다.

핵심 개념

노드와 링크

단일 연결 리스트 (singly linked)

head
 │
 ▼
┌───┬───┐   ┌───┬───┐   ┌───┬───┐
│ A │ ●─┼──▶│ B │ ●─┼──▶│ C │ ∅ │
└───┴───┘   └───┴───┘   └───┴───┘
 val next

이중 연결 리스트 (doubly linked)

∅ ◀─┼ A ┼─▶ ◀─┼ B ┼─▶ ◀─┼ C ┼─▶ ∅
   prev next

단일 연결 리스트는 노드가 next 하나만 가진다. 이중 연결 리스트는 prev 도 가져서 양쪽으로 움직일 수 있고, 노드 하나를 손에 쥐고 있으면 그 노드를 O(1) 에 뺄 수 있다. 단일 연결 리스트에서 노드를 빼려면 그 앞 노드를 알아야 하므로, 앞 노드를 모르면 처음부터 찾아가야 한다.

연산 비용

연산 배열(동적) 단일 연결 이중 연결
i 번째 접근 O(1) O(n) O(n)
맨 앞 삽입·삭제 O(n) O(1) O(1)
맨 뒤 삽입 분할 상환 O(1) O(1) (tail 포인터 있을 때) O(1)
맨 뒤 삭제 O(1) O(n) O(1)
노드를 알 때 그 자리 삽입·삭제 O(n) 뒤에 삽입 O(1), 삭제는 앞 노드 필요 O(1)
값으로 찾기 O(n) O(n) O(n)
원소당 추가 메모리 0 (+여유 용량) 포인터 1개 포인터 2개

표에서 자주 놓치는 점이 있다. “중간 삽입 O(1)” 은 그 위치의 노드를 이미 알고 있을 때만 참이다. “앞에서 500번째에 넣어라” 는 500번 따라가는 O(n) 이 먼저 든다. 그래서 연결 리스트가 빛나는 곳은 “노드 참조를 다른 곳(해시 테이블 등)에 저장해 두고 그걸로 바로 빼는” 패턴이다. LRU 캐시가 정확히 이 구조다.

센티널(sentinel) 노드

빈 리스트, 첫 노드, 마지막 노드를 따로 처리하다 보면 if head is None 같은 분기가 곳곳에 생긴다. 값이 없는 가짜 노드 하나를 두고 리스트를 원형으로 이어 두면, 모든 노드가 항상 앞과 뒤를 가지게 되어 분기가 사라진다.

        ┌──────────────────────────────┐
        ▼                              │
   [센티널] ⇄ [A] ⇄ [B] ⇄ [C] ⇄ ───────┘
   (빈 리스트면 센티널이 자기 자신을 가리킴)

리눅스 커널의 struct list_head 가 이 방식이다. 커널 문서는 커널의 이중 연결 리스트가 원형이어서 머리에서 꼬리로 한 번 뒤로 가면 된다고 설명한다(Linux Kernel — Linked Lists in Linux).

침습형(intrusive) 리스트

일반 라이브러리의 연결 리스트는 노드가 값을 감싼다. 커널의 리스트는 반대로, 데이터 구조체 안에 list_head 멤버를 심는다. 이렇게 하면 노드를 위해 메모리를 따로 할당하지 않아도 되고, 한 객체에 list_head 를 여러 개 두어 여러 목록에 동시에 걸 수 있다. 예를 들어 같은 프로세스 구조체가 “전체 목록”과 “실행 대기 목록”에 함께 걸리는 식이다. 연결 리스트가 오늘날에도 쓰이는 대표적인 이유다.

왜 실무에서 덜 쓰이나

러스트 표준 라이브러리 문서는 LinkedList 항목에 “배열 기반 컨테이너가 일반적으로 더 빠르고 메모리 효율적이며 CPU 캐시를 더 잘 쓰므로, 거의 항상 Vec 이나 VecDeque 를 쓰는 편이 낫다”고 적어 두었다(Rust LinkedList). 이유는 세 가지다.

  1. 캐시 지역성. 노드가 힙 여기저기에 흩어져 있어 다음 노드로 갈 때마다 캐시 미스가 날 수 있다.
  2. 메모리 오버헤드. 원소마다 포인터 1~2개, 그리고 할당기 머리 정보가 붙는다. 작은 정수 하나를 담는데 몇 배의 메모리를 쓴다.
  3. 할당 비용. 삽입마다 메모리 할당이 한 번씩 일어난다.

반대로 같은 문서는 연결 리스트를 쓸 때로 “리스트를 효율적으로 쪼개고 이어 붙여야 할 때”, “분할 상환을 용납할 수 없을 때”를 든다(Rust std::collections). 두 리스트를 잇는 연산은 연결 리스트에서 포인터 몇 개로 끝나지만, 배열에서는 복사가 필요하다.

직접 해 보기

센티널을 쓰는 원형 이중 연결 리스트를 만든다. 삽입·삭제 함수에 if 가 하나도 없다는 점을 보자.

class Node:
    __slots__ = ("val", "prev", "next")
    def __init__(self, val=None):
        self.val, self.prev, self.next = val, None, None

class DList:
    """센티널 하나를 쓰는 원형 이중 연결 리스트"""
    def __init__(self):
        self.head = Node()                 # 값 없는 센티널
        self.head.prev = self.head.next = self.head
        self.size = 0

    def _insert_after(self, node, new):    # O(1)
        new.prev, new.next = node, node.next
        node.next.prev = new
        node.next = new
        self.size += 1
        return new

    def push_front(self, v): return self._insert_after(self.head, Node(v))
    def push_back(self, v):  return self._insert_after(self.head.prev, Node(v))

    def remove(self, node):                # 노드를 알면 O(1)
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1
        return node.val

    def __iter__(self):
        cur = self.head.next
        while cur is not self.head:
            yield cur.val
            cur = cur.next

    def reverse(self):                     # 각 노드의 prev/next 교환
        cur = self.head
        while True:
            cur.prev, cur.next = cur.next, cur.prev
            cur = cur.prev                 # 교환 뒤라 prev 가 원래 next
            if cur is self.head:
                break

L = DList()
for x in "BCD":
    L.push_back(x)
a = L.push_front("A")
L.push_back("E")
print(list(L), L.size)
L.remove(a)
print(list(L), L.size)
L.reverse()
print(list(L))

['A', 'B', 'C', 'D', 'E'] 5
['B', 'C', 'D', 'E'] 4
['E', 'D', 'C', 'B']

push_front 가 돌려준 노드 a 를 들고 있다가 remove(a) 로 바로 뺐다. 탐색이 없다. 이것이 “노드를 알면 O(1)” 의 실제 모습이다.

백만 개를 넣고 sum 으로 훑어 보면, 같은 환경에서 파이썬 list 는 약 16ms, 위 DList 는 약 115ms 였다. 다만 이 차이의 대부분은 캐시가 아니라 파이썬 제너레이터와 속성 접근 비용이다. 캐시 지역성 차이를 순수하게 보려면 C 나 러스트로 재야 한다. 측정이 무엇을 재는지 구분하는 습관이 중요하다.

현업에서는

  • 커널과 시스템 코드. 리눅스 커널은 프로세스, 타이머, 장치 목록 등 수많은 곳에 침습형 이중 연결 리스트를 쓴다. 할당 없이 O(1) 로 목록 사이를 옮겨 다닐 수 있기 때문이다.
  • LRU 캐시. 해시 맵이 노드 참조를 들고, 이중 연결 리스트가 사용 순서를 든다. 자바의 LinkedHashMap 이 바로 해시 테이블에 이중 연결 리스트를 얹은 구조다. 이 시리즈의 LRU 캐시 편에서 직접 만든다.
  • 자바 LinkedList. 자바 문서는 이것을 List 와 Deque 를 구현한 이중 연결 리스트라고 정의한다(Java SE 21 LinkedList). 그러나 인덱스 접근 get(i) 은 끝에서부터 따라가므로 O(n) 이다. for (int i...) list.get(i) 루프는 O(n²) 이 된다. 리뷰에서 자주 지적되는 패턴이다.
  • 면접 단골. 뒤집기, 가운데 찾기(느린·빠른 포인터), 사이클 탐지는 포인터 조작 능력을 보는 문제로 자주 나온다. 실무 빈도와 별개로 사고 훈련으로서 가치가 있다.

확인 문제

  1. 단일 연결 리스트에서 노드 X 를 손에 쥐고 있을 때, X 뒤에 삽입과 X 자체 삭제의 비용은 각각 얼마인가?
  2. 센티널 노드를 두면 어떤 코드가 사라지는가?
  3. “연결 리스트는 중간 삽입이 O(1) 이다” 라는 말에 빠진 조건은?
  4. 침습형 리스트가 일반 리스트보다 나은 점 두 가지는?
  5. 자바 LinkedList 를 for (int i = 0; i < n; i++) list.get(i) 로 훑으면 전체 비용은?

풀이

  1. 뒤에 삽입은 O(1). 자기 자신 삭제는 앞 노드를 알아야 하므로 일반적으로 O(n). (다음 노드의 값을 복사해 오고 다음 노드를 지우는 꼼수가 있지만 마지막 노드에는 못 쓴다.)
  2. 빈 리스트, 첫 노드, 마지막 노드에 대한 None 검사 분기가 사라진다.
  3. 삽입할 위치의 노드를 이미 알고 있어야 한다. 모르면 찾는 데 O(n) 이 든다.
  4. 노드 할당이 따로 없고, 한 객체를 여러 리스트에 동시에 걸 수 있다.
  5. get(i) 가 매번 O(min(i, n-i)) 이므로 전체 O(n²).

더 읽을거리 (References)