연결 리스트란 무엇인가

1. 연속된 공간이 불편한 이유

배열은 중간에 원소를 끼워 넣거나 빼면 뒤쪽을 전부 한 칸씩 밀거나 당겨야 해서 O(n)이 듭니다. 원소를 빈틈없이 붙여 두기로 했기 때문에 생기는 비용입니다.

또 크기 n짜리 배열을 만들려면 메모리에 n칸이 연속으로 비어 있어야 합니다. 전체 여유 공간이 충분해도 연속된 자리가 없으면 잡지 못합니다.

연결 리스트는 원소를 연속된 공간에 두지 않습니다. 대신 각 원소가 다음 원소의 위치를 들고 있게 해서 순서를 유지합니다.

2. 정의

연결 리스트의 원소 하나를 노드(node)라고 하고, 노드는 값인 키(key)와 다음 노드를 가리키는 링크(link)로 이루어집니다. 첫 노드를 head, 마지막 노드를 tail이라 하고, 원소 개수는 size로 따로 관리합니다.

head                                  tail
  |                                     |
  v                                     v
+------+    +------+    +------+    +------+
| 3  *-|--> | 10 *-|--> | 5  *-|--> | 8  / |
+------+    +------+    +------+    +------+
 key link                            link = None

size = 4

노드들은 메모리 여기저기에 흩어져 있어도 됩니다. 링크가 순서를 대신 기억하기 때문입니다.

링크가 한 방향으로만 있으면 단방향(한방향) 연결 리스트, 앞뒤 양쪽을 모두 가리키면 양방향 연결 리스트입니다. 양방향 노드는 키 하나에 링크 두 개를 가집니다.

class Node:
    def __init__(self, key=None):
        self.key = key
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

3. 탐색

배열은 인덱스로 주소를 계산해 바로 접근했지만, 연결 리스트에는 그런 계산이 없습니다. 특정 노드의 값을 알려면 head부터 링크를 하나씩 따라가야 하므로 상수 시간이 아닙니다.

def search(self, key):
    v = self.head
    while v is not None:
        if v.key == key:
            return v
        v = v.next          # 링크를 따라 한 칸 이동
    return None

최악에는 끝까지 가므로 O(n)이고, k번째 노드에 접근하는 것도 같은 이유로 O(k)입니다.

순회하는 코드는 탐색, 출력, 개수 세기마다 똑같이 반복됩니다. 제너레이터로 한 번만 정의해 두면 for문으로 쓸 수 있습니다.

def __iter__(self):
    v = self.head
    while v is not None:
        yield v
        v = v.next

# 사용
for v in L:
    print(v.key)

제너레이터는 노드를 미리 전부 모아 두지 않고 요청받을 때 하나씩 넘겨줍니다. 그래서 추가 메모리가 거의 들지 않고, 원하는 값을 찾으면 도중에 멈출 수 있습니다.

4. 양 끝에서의 삽입과 삭제

연결 리스트에서 가장 많이 쓰는 연산은 양 끝에서의 삽입과 삭제입니다.

• PushFront(key): 맨 앞에 삽입
• PushBack(key): 맨 뒤에 삽입
• PopFront(): 맨 앞 노드 삭제
• PopBack(): 맨 뒤 노드 삭제

before: PushFront(1)

head
  v
+------+    +------+    +------+
| 3  *-|--> | 10 *-|--> | 5  / |
+------+    +------+    +------+

after

head
  v
+------+    +------+    +------+    +------+
| 1  *-|--> | 3  *-|--> | 10 *-|--> | 5  / |
+------+    +------+    +------+    +------+

def push_front(self, key):
    v = Node(key)
    v.next = self.head
    self.head = v
    if self.tail is None:              # 비어 있었다면 tail도 같이
        self.tail = v
    self.size += 1

def push_back(self, key):
    v = Node(key)
    if self.tail is None:              # 비어 있으면 head도 같이
        self.head = v
    else:
        self.tail.next = v             # 끝에 이어 붙이고
    self.tail = v                      # tail만 옮긴다
    self.size += 1

삽입 쪽은 둘 다 링크 한두 개만 바꾸므로 O(1)입니다. PushBack이 O(1)인 것은 tail을 들고 있기 때문이고, tail이 없으면 끝까지 따라가야 해서 O(n)이 됩니다.

def pop_front(self):
    if self.head is None:
        raise IndexError("빈 리스트")
    key = self.head.key
    self.head = self.head.next
    if self.head is None:              # 마지막 원소를 뺐다면
        self.tail = None
    self.size -= 1
    return key

def pop_back(self):
    if self.head is None:
        raise IndexError("빈 리스트")
    if self.head is self.tail:         # 원소가 하나뿐
        key = self.head.key
        self.head = None
        self.tail = None
        self.size -= 1
        return key
    prev = self.head
    while prev.next is not self.tail:  # tail 앞 노드를 찾는다
        prev = prev.next
    key = self.tail.key
    prev.next = None
    self.tail = prev
    self.size -= 1
    return key

PopFront는 head만 옮기면 되어 O(1)입니다. PopBack만 다릅니다. 마지막 노드를 지우려면 그 앞 노드의 링크를 None으로 바꿔야 하는데, 단방향 링크로는 tail에서 앞으로 되돌아갈 수 없습니다. 그래서 while문으로 head부터 훑어 tail 앞 노드를 찾아야 하고, 이 한 줄 때문에 PopBack이 O(n)이 됩니다.

5. 삽입

배열과 달리 연결 리스트의 삽입은 링크 몇 개만 바꾸면 끝나므로 상수 시간입니다. 뒤 원소를 미는 일이 없습니다.

before: 노드 10 뒤에 7을 넣기

+------+    +------+    +------+
| 3  *-|--> | 10 *-|--> | 5  / |
+------+    +------+    +------+

after

+------+    +------+       +------+
| 3  *-|--> | 10 *-|--+ +->| 5  / |
+------+    +------+  | |  +------+
                      | |
                      v |
                   +------+
                   | 7  *-|
                   +------+

def insert_after(self, v, key):
    w = Node(key)
    w.next = v.next     # 새 노드가 뒤를 가리키고
    v.next = w          # 앞 노드가 새 노드를 가리킨다
    self.size += 1

맨 앞 삽입도 head만 바꾸면 되어 O(1)이고, tail을 들고 있으면 맨 뒤 삽입도 O(1)입니다.

6. 삭제

삭제도 링크 하나를 건너뛰게 바꾸면 됩니다.

before: 노드 10 뒤의 7을 삭제

+------+    +------+    +------+    +------+
| 3  *-|--> | 10 *-|--> | 7  *-|--> | 5  / |
+------+    +------+    +------+    +------+

after

+------+    +------+                +------+
| 3  *-|--> | 10 *-|--------------->| 5  / |
+------+    +------+                +------+
                          7은 아무도 가리키지 않음

def delete_after(self, v):
    w = v.next
    if w is None:
        return None
    v.next = w.next
    self.size -= 1
    return w.key

여기서 단방향의 한계가 드러납니다. 삭제하려는 노드 자체를 알아도 그 앞 노드를 모르면 링크를 고칠 수 없어서, head부터 다시 찾아야 합니다. 그래서 "노드 x를 삭제"는 단방향에서 O(n)입니다. 앞서 PopBack이 O(n)이었던 것도 같은 이유입니다.

7. 시간복잡도