연결 리스트

노드 — 연결 리스트의 기본 단위

연결 리스트의 각 원소를 노드(node)라 부른다. 노드는 두 가지를 담고 있다.

• 데이터 필드 — 실제 저장할 값.
• 포인터 필드 — 다음 노드(또는 이전 노드)의 메모리 주소.

C로 표현하면 다음과 같다.

typedef struct Node {
    int data;
    struct Node *next;
} Node;

next 포인터가 다음 노드의 주소를 가리키고, 리스트의 마지막 노드는 next가 NULL이다. 이 단순한 구조 하나가 연결 리스트 전체를 지탱한다.

단일 연결 리스트

단일 연결 리스트singly linked list는 각 노드가 next 포인터 하나만 가지는 가장 기본적인 형태다. 리스트의 시작점인 head 포인터 하나로 전체 리스트에 접근한다.

핵심 연산

헤드 삽입

새 노드의 next를 현재 head로 설정한 뒤, head를 새 노드로 갱신한다. 다른 노드를 건드릴 필요가 없으므로 $O(1)$의 시간복잡도를 가진다.

def prepend(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node

헤드 삭제

head를 head.next로 갱신하면 끝이다. 시간복잡도는 역시 $O(1)$이다.

탐색

원하는 값을 찾으려면 head부터 시작하여 next를 따라 하나씩 순회해야 한다. 최악의 경우 리스트 끝까지 가야 하므로 시간복잡도는 $O(n)$이다.

def search(self, key):
    current = self.head
    while current is not None:
        if current.data == key:
            return current
        current = current.next
    return None

임의 위치 삽입/삭제

삽입하거나 삭제할 위치의 바로 앞 노드를 알고 있다면 포인터만 바꾸면 되므로 시간복잡도는 $O(1)$이다. 하지만 그 위치를 찾기 위해 순회가 필요하면 시간복잡도는 $O(n)$이 된다.

한계

단일 연결 리스트는 앞에서 뒤로만 이동할 수 있다. 특정 노드를 삭제하려면 그 앞 노드를 알아야 next 포인터를 갱신할 수 있는데, 뒤로 돌아갈 방법이 없으니 처음부터 다시 순회해야 한다. 이 한계를 해결하는 것이 이중 연결 리스트다.

이중 연결 리스트

이중 연결 리스트doubly linked list는 각 노드가 next와 prev 두 포인터를 가진다. 앞뒤 양방향으로 이동할 수 있으므로, 삭제할 노드의 참조만 있으면 앞 노드를 따로 찾을 필요 없이 바로 삭제할 수 있다.

각 노드를 prev, key, next 세 필드로 표현한다. 리스트의 첫 노드의 prev는 NIL이고, 마지막 노드의 next도 NIL이다.

핵심 연산

의사코드를 기반으로 핵심 연산을 살펴보자.

삽입 (LIST-PREPEND)

새 노드 $x$를 리스트의 맨 앞에 삽입한다.

$$\begin{aligned} &\texttt{LIST-PREPEND}(L, x) \\ &\quad x.next = L.head \\ &\quad x.prev = \texttt{NIL} \\ &\quad \textbf{if } L.head \neq \texttt{NIL} \\ &\quad\quad L.head.prev = x \\ &\quad L.head = x \end{aligned}$$

새 노드의 next를 현재 head로, prev를 NIL로 설정한 뒤, 기존 head의 prev를 새 노드로 갱신하고 head를 새 노드로 바꾼다. 시간복잡도는 $O(1)$이다.

탐색 (LIST-SEARCH)

키 $k$를 가진 노드를 찾을 때까지 next를 따라 순회한다.

$$\begin{aligned} &\texttt{LIST-SEARCH}(L, k) \\ &\quad x = L.head \\ &\quad \textbf{while } x \neq \texttt{NIL} \textbf{ and } x.key \neq k \\ &\quad\quad x = x.next \\ &\quad \textbf{return } x \end{aligned}$$

최악의 경우 시간복잡도는 $O(n)$이다. 단일 연결 리스트와 동일하다.

삭제 (LIST-DELETE)

노드 $x$의 참조가 주어졌을 때, 해당 노드를 리스트에서 제거한다.

$$\begin{aligned} &\texttt{LIST-DELETE}(L, x) \\ &\quad \textbf{if } x.prev \neq \texttt{NIL} \\ &\quad\quad x.prev.next = x.next \\ &\quad \textbf{else } L.head = x.next \\ &\quad \textbf{if } x.next \neq \texttt{NIL} \\ &\quad\quad x.next.prev = x.prev \end{aligned}$$

$x$의 앞 노드와 뒷 노드를 서로 연결하면 $x$가 리스트에서 빠진다. 노드 $x$의 참조가 이미 주어져 있으므로 시간복잡도는 $O(1)$이다. 단, 값으로 삭제하려면 먼저 탐색이 필요하므로 이때 시간복잡도는 $O(n)$이 된다.

이 의사코드에서 x.prev와 x.next가 NIL인지 매번 확인하는 점에 주목하면 좋다. 첫 노드를 삭제할 때는 L.head를, 마지막 노드를 삭제할 때는 앞 노드의 next를 각각 특별하게 처리해야 하기 때문이다. 이 경계 조건 처리를 없애는 기법이 센티널이다.

센티널을 이용한 원형 이중 연결 리스트

센티널(sentinel)은 실제 데이터를 담지 않는 더미 노드(dummy node)로, 리스트의 경계 조건을 단순화하기 위해 사용한다. 이 센티널 노드를 보통 $L.nil$이라 부른다.

$L.nil$은 head와 tail 사이에 위치하여, $L.nil.next$가 리스트의 첫 노드를, $L.nil.prev$가 리스트의 마지막 노드를 가리킨다. 리스트가 비어 있으면 $L.nil.next$와 $L.nil.prev$가 모두 $L.nil$ 자신을 가리켜 원형 구조를 이룬다.

센티널을 도입하면 NIL 검사가 사라지고 코드가 간결해진다.

$$\begin{aligned} &\texttt{LIST-PREPEND}'(L, x) \\ &\quad x.next = L.nil.next \\ &\quad x.prev = L.nil \\ &\quad L.nil.next.prev = x \\ &\quad L.nil.next = x \end{aligned}$$ $$\begin{aligned} &\texttt{LIST-DELETE}'(L, x) \\ &\quad x.prev.next = x.next \\ &\quad x.next.prev = x.prev \end{aligned}$$

LIST-DELETE'가 단 두 줄로 줄어들었다. x가 첫 노드든 마지막 노드든, $L.nil$이 양쪽 끝을 감싸고 있으므로 prev나 next가 NIL일 가능성 자체가 사라진다.

센티널이 NIL 조건 분기를 제거해 코드를 간결하게 만들지만, 노드가 매우 적은 짧은 리스트가 많다면 센티널 노드의 추가 메모리가 낭비될 수 있다. 센티널은 코드 단순화에 의의가 있지, 시간 복잡도 자체를 개선하지는 않는다¹.

배열 vs. 연결 리스트

배열과 연결 리스트는 선형 자료구조의 양대 구현이다. 어떤 연산이 빈번한지에 따라 선택이 달라진다.

배열은 원소가 메모리에 연속적으로 배치되어 캐시 지역성³이 뛰어나고, 인덱스로 $O(1)$ 접근이 가능하다. 반면 중간 삽입/삭제 시에는 원소를 이동시켜야 하므로 $O(n)$이 든다.

연결 리스트는 삽입/삭제 위치의 노드만 알면 포인터 조작으로 $O(1)$에 처리할 수 있지만, $k$번째 원소에 접근하려면 처음부터 $k$번 순회해야 하므로 $O(n)$의 시간복잡도를 가진다. 또한 노드마다 포인터를 저장해야 하므로 메모리 오버헤드가 있고, 노드가 메모리 곳곳에 흩어져 캐시 미스가 자주 발생한다.

연결 리스트와 다른 자료구조의 관계

연결 리스트는 다른 자료구조를 구현하는 재료로 자주 쓰인다.

스택은 연결 리스트의 head에서만 삽입/삭제하면 LIFO 정책이 자연스럽게 구현된다. 큐는 head에서 dequeue, tail에서 enqueue하면 FIFO가 된다. 해시 테이블에서 충돌을 처리하는 가장 기본적인 방법인 체이닝chaining은 각 버킷을 연결 리스트로 관리한다.

운영체제에서도 연결 리스트는 핵심적인 역할을 한다. 리눅스 커널의 태스크 리스트는 task_struct 구조체들의 원형 이중 연결 리스트로 구성되어 있으며, 스케줄러의 준비 큐ready queue도 연결 리스트 기반으로 관리된다. 데이터베이스에서는 B+ Tree의 리프 노드들이 연결 리스트로 연결되어 범위 검색range query을 효율적으로 수행한다.

Python collections.deque

Python에서 연결 리스트를 직접 구현할 수도 있지만, 실무에서는 collections.deque가 연결 리스트의 역할을 대신한다. deque는 내부적으로 이중 연결된 고정 크기 블록 배열⁴로 구현되어 있어, 양쪽 끝에서 $O(1)$ 삽입/삭제를 보장하면서도 캐시 지역성이 순수 연결 리스트보다 우수하다.

from collections import deque

d = deque([1, 2, 3])
d.appendleft(0)    # 왼쪽 삽입: deque([0, 1, 2, 3])
d.append(4)        # 오른쪽 삽입: deque([0, 1, 2, 3, 4])
d.popleft()        # 왼쪽 삭제: 0 반환
d.pop()            # 오른쪽 삭제: 4 반환

단, deque는 중간 인덱스 접근이 $O(n)$이므로 인덱스 기반 접근이 빈번하다면 list(동적 배열)가 적합하다.

---

출처

• Cormen, T. H. et al. (2022) Introduction to Algorithms. 4th edn. Cambridge, MA: MIT Press. Chapter 10.2.
• Kamran, A. (2022) 전문가를 위한 C (박지윤, Trans.; 1st edn). 한빛미디어.
• Python Software Foundation (2025) collections.deque. Available at: https://docs.python.org/3/library/collections.html#collections.deque.

Footnotes

1. 센티널의 트레이드오프 — 센티널은 코드의 조건 분기를 줄여 가독성을 높이지만, 리스트마다 추가 노드를 할당해야 한다. 짧은 리스트가 수천 개 존재하는 상황(예: 해시 테이블의 버킷)에서는 이 오버헤드가 누적될 수 있다. Cormen et al. (2022), p. 261 참조. ↩

2. 배열의 헤드 삽입이 $O(n)$인 이유 — 배열의 맨 앞에 원소를 넣으려면 기존 원소를 전부 한 칸씩 뒤로 밀어야 하기 때문이다. 동적 배열의 append(끝 삽입)는 상각 $O(1)$이지만, insert(0, x)는 항상 $O(n)$이다. ↩

3. 캐시 지역성(cache locality) — CPU 캐시가 인접한 메모리 주소를 미리 적재하는 특성. 배열은 원소가 연속된 메모리에 저장되어 캐시 히트율이 높지만, 연결 리스트는 노드가 메모리 곳곳에 흩어져 캐시 미스가 자주 발생한다. ↩

4. CPython의 deque 구현 — 내부적으로 64개 원소를 담는 고정 크기 블록들을 이중 연결 리스트로 연결한 구조다. 블록 내부에서는 배열처럼 연속 메모리를 사용하므로, 순수 노드 기반 연결 리스트보다 캐시 지역성이 좋다. CPython 소스 Modules/_collectionsmodule.c 참조. ↩