> [!abstract] Introduction > 배열은 원소들이 메모리에 빈틈없이 나란히 놓여 있는 자료구조입니다. 덕분에 인덱스 하나로 원하는 원소에 바로 접근할 수 있지만, 중간에 원소를 넣거나 빼려면 나머지 원소를 전부 밀거나 당겨야 합니다. 연결 리스트*Linked List*는 이 문제를 해결합니다. ## 노드 — 연결 리스트의 기본 단위 연결 리스트의 각 원소를 **노드**(*node*)라 부른다. 노드는 두 가지를 담고 있다. - **데이터 필드** — 실제 저장할 값. - **포인터 필드** — 다음 노드(또는 이전 노드)의 메모리 주소. C로 표현하면 다음과 같다. ```c typedef struct Node { int data; struct Node *next; } Node; ``` `next` 포인터가 다음 노드의 주소를 가리키고, 리스트의 마지막 노드는 `next`가 `NULL`이다. 이 단순한 구조 하나가 연결 리스트 전체를 지탱한다. ## 단일 연결 리스트 단일 연결 리스트*singly linked list*는 각 노드가 `next` 포인터 하나만 가지는 가장 기본적인 형태다. 리스트의 시작점인 `head` 포인터 하나로 전체 리스트에 접근한다. ![[singlyLinkedList.svg]] ### 핵심 연산 #### 헤드 삽입 새 노드의 `next`를 현재 `head`로 설정한 뒤, `head`를 새 노드로 갱신한다. 다른 노드를 건드릴 필요가 없으므로 $O(1)$의 시간복잡도를 가진다. ```python 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)$이다. ```python 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` 두 포인터를 가진다. 앞뒤 양방향으로 이동할 수 있으므로, 삭제할 노드의 참조만 있으면 앞 노드를 따로 찾을 필요 없이 바로 삭제할 수 있다. ![[doublyLinkedList.svg]] 각 노드를 `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$이라 부른다. ![[sentinelLinkedList.svg]] $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` 조건 분기를 제거해 코드를 간결하게 만들지만, 노드가 매우 적은 짧은 리스트가 많다면 센티널 노드의 추가 메모리가 낭비될 수 있다. 센티널은 코드 단순화에 의의가 있지, 시간 복잡도 자체를 개선하지는 않는다[^sentinel-tradeoff]. ## 배열 vs. 연결 리스트 배열과 연결 리스트는 선형 자료구조의 양대 구현이다. 어떤 연산이 빈번한지에 따라 선택이 달라진다. | 연산 | 배열 | 연결 리스트 (노드 참조 있음) | | ----------- | -------------------- | ----------------- | | 인덱스 접근 | $O(1)$ | $O(n)$ | | 헤드 삽입/삭제 | $O(n)$[^array-shift] | $O(1)$ | | 임의 위치 삽입/삭제 | $O(n)$ | $O(1)$ | | 탐색 | $O(n)$ | $O(n)$ | | 캐시 지역성 | 우수 | 불리 | | 메모리 오버헤드 | 없음 (또는 미사용 공간) | 노드당 포인터 1~2개 | **배열**은 원소가 메모리에 연속적으로 배치되어 캐시 지역성[^cache-locality]이 뛰어나고, 인덱스로 $O(1)$ 접근이 가능하다. 반면 중간 삽입/삭제 시에는 원소를 이동시켜야 하므로 $O(n)$이 든다. **연결 리스트**는 삽입/삭제 위치의 노드만 알면 포인터 조작으로 $O(1)$에 처리할 수 있지만, $k$번째 원소에 접근하려면 처음부터 $k$번 순회해야 하므로 $O(n)$의 시간복잡도를 가진다. 또한 노드마다 포인터를 저장해야 하므로 메모리 오버헤드가 있고, 노드가 메모리 곳곳에 흩어져 캐시 미스가 자주 발생한다. ## 연결 리스트와 다른 자료구조의 관계 연결 리스트는 다른 자료구조를 **구현**하는 재료로 자주 쓰인다. [[Stack|스택]]은 연결 리스트의 `head`에서만 삽입/삭제하면 LIFO 정책이 자연스럽게 구현된다. [[Queue|큐]]는 `head`에서 `dequeue`, `tail`에서 `enqueue`하면 FIFO가 된다. [[Hashing|해시 테이블]]에서 충돌을 처리하는 가장 기본적인 방법인 체이닝*chaining*은 각 버킷을 연결 리스트로 관리한다. 운영체제에서도 연결 리스트는 핵심적인 역할을 한다. 리눅스 커널의 [[Process Control Block|태스크 리스트]]는 `task_struct` 구조체들의 원형 이중 연결 리스트로 구성되어 있으며, [[Scheduler|스케줄러]]의 준비 큐*ready queue*도 연결 리스트 기반으로 관리된다. 데이터베이스에서는 [[B+ Tree]]의 리프 노드들이 연결 리스트로 연결되어 범위 검색*range query*을 효율적으로 수행한다. ## Python `collections.deque` Python에서 연결 리스트를 직접 구현할 수도 있지만, 실무에서는 `collections.deque`가 연결 리스트의 역할을 대신한다. `deque`는 내부적으로 이중 연결된 고정 크기 블록 배열[^deque-impl]로 구현되어 있어, 양쪽 끝에서 $O(1)$ 삽입/삭제를 보장하면서도 캐시 지역성이 순수 연결 리스트보다 우수하다. ```python 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. [^sentinel-tradeoff]: 센티널의 트레이드오프 — 센티널은 코드의 조건 분기를 줄여 가독성을 높이지만, 리스트마다 추가 노드를 할당해야 한다. 짧은 리스트가 수천 개 존재하는 상황(예: 해시 테이블의 버킷)에서는 이 오버헤드가 누적될 수 있다. Cormen et al. (2022), p. 261 참조. [^array-shift]: 배열의 헤드 삽입이 $O(n)$인 이유 — 배열의 맨 앞에 원소를 넣으려면 기존 원소를 전부 한 칸씩 뒤로 밀어야 하기 때문이다. 동적 배열의 `append`(끝 삽입)는 상각 $O(1)$이지만, `insert(0, x)`는 항상 $O(n)$이다. [^cache-locality]: 캐시 지역성(*cache locality*) — CPU 캐시가 인접한 메모리 주소를 미리 적재하는 특성. 배열은 원소가 연속된 메모리에 저장되어 캐시 히트율이 높지만, 연결 리스트는 노드가 메모리 곳곳에 흩어져 캐시 미스가 자주 발생한다. [^deque-impl]: CPython의 `deque` 구현 — 내부적으로 64개 원소를 담는 고정 크기 블록들을 이중 연결 리스트로 연결한 구조다. 블록 내부에서는 배열처럼 연속 메모리를 사용하므로, 순수 노드 기반 연결 리스트보다 캐시 지역성이 좋다. CPython 소스 `Modules/_collectionsmodule.c` 참조.