thenullpage.com
1. 값 옆에 다음 자리를 적어두는 구조
연결 리스트(linked list)는 값들을 나란히 붙여 담지 않는 자료구조입니다. 값 하나와 다음 값이 놓인 자리를 한 묶음으로 보관하고, 이 묶음을 노드(node)라고 부릅니다. 노드가 메모리 여기저기 흩어져 있어도 각자 다음 위치를 들고 있으니 첫 노드부터 따라가면 전체를 훑을 수 있습니다.
보물찾기 쪽지와 같습니다. 쪽지마다 값과 다음 쪽지의 위치가 적혀 있고, 마지막 쪽지에는 위치 대신 없음이라는 표시가 들어갑니다. 파이썬에서는 이 없음을 None으로 씁니다.
2. 노드를 직접 만들어 이어보기
노드는 값을 담는 칸과 다음 노드를 가리키는 칸을 가진 작은 상자입니다. 클래스로 옮겨보겠습니다.
class Node:
def __init__(self, value):
self.value = value
self.next = None
a = Node(10)
b = Node(20)
c = Node(30)
a.next = b
b.next = c
node = a
while node is not None:
print(node.value)
node = node.next
10
20
30
노드 세 개를 만들고 next에 다음 노드를 넣어 사슬로 엮었습니다. 마지막 노드 c의 next는 None이라 따라가다 None을 만나면 반복문이 저절로 멈춥니다. 첫 노드 a는 head라고 부르고, 손에 쥐는 것은 이 head 하나뿐입니다.
3. 세 번째 값을 꺼내는 데 걸리는 시간
파이썬 리스트에서 nums[2]는 시작 자리에 칸 크기를 곱해 더하는 계산 한 번이면 끝납니다. 연결 리스트는 노드가 어디에 흩어져 있는지 알 수 없으니 첫 노드부터 실제로 따라가야 합니다.
def get(head, index):
node = head
for _ in range(index):
if node is None:
return None
node = node.next
return node.value
print(get(a, 0))
print(get(a, 2))
10
30
백 번째 값이 필요하면 백 번 이동해야 하고, 값이 들어 있는지 보는 탐색도 처음부터 훑어야 합니다. 둘 다 개수 n에 비례하니 O(n)입니다.
4. 대신 맨 앞에 넣고 빼는 것이 아주 쌉니다
배열은 맨 앞에 값을 끼우려면 뒤의 값을 전부 한 칸씩 밀어야 합니다. 연결 리스트는 밀 것이 없습니다. 새 노드가 기존 첫 노드를 가리키게 하고 시작점만 옮기면 됩니다.
def push_front(head, value):
node = Node(value)
node.next = head
return node
head = push_front(a, 5)
print(head.value, head.next.value)
5 10
노드가 열 개든 백만 개든 실행되는 줄은 세 줄이라 O(1)입니다. 위치만 알면 그 자리에 넣고 빼기가 값싸다는 점이 연결 리스트의 존재 이유입니다.
5. 삭제할 때는 지울 노드가 아니라 그 앞 노드가 필요합니다
노드를 사슬에서 빼내려면 그 노드를 가리키던 앞 노드의 화살표를 다음 노드로 돌려야 합니다. 앞 노드를 모르면 고칠 방법이 없어서, 삭제 코드는 직전 노드를 붙잡고 움직입니다.
def remove(head, value):
dummy = Node(None)
dummy.next = head
prev = dummy
while prev.next is not None:
if prev.next.value == value:
prev.next = prev.next.next
break
prev = prev.next
return dummy.next
head = remove(a, 20)
node = head
while node is not None:
print(node.value, end=" ")
10 30
실제 삭제는 prev.next = prev.next.next 한 줄이 전부입니다. 20이 담긴 노드는 그대로 남아 있지만 아무도 가리키지 않게 되어 사슬에서 떨어져 나갑니다.
맨 앞에 붙인 dummy는 값이 없는 가짜 노드입니다. 이것이 없으면 첫 노드를 지울 때만 head 자체를 바꿔야 해서 조건문이 하나 더 붙습니다. 가짜를 한 칸 세워두면 모든 노드가 앞 노드를 가지게 되어 그 예외가 사라집니다. 더미 노드라고 부르는 이 수법이 실수를 줄이는 가장 쉬운 방법입니다.
6. 화살표 방향을 하나씩 돌려 뒤집기
뒤집기는 면접에서 가장 자주 나오는 연습 문제입니다. 새 노드를 만들지 않고 화살표 방향만 반대로 돌리면 됩니다.
def reverse(head):
prev = None
node = head
while node is not None:
next_node = node.next
node.next = prev
prev = node
node = next_node
return prev
head = reverse(head)
print(head.value, head.next.value)
30 10
순서가 중요합니다. node.next = prev로 화살표를 돌리는 순간 다음 노드로 가는 길이 끊기니, 그 전에 next_node에 다음 노드를 챙겨둬야 합니다. 한 번만 훑으니 O(n)이고 변수는 세 개뿐이라 메모리는 O(1)입니다.
7. 속도가 다른 두 포인터로 알아내는 것들
노드를 가리키는 변수를 포인터라고 부릅니다. 포인터 두 개를 다른 속도로 움직이면 한 번 훑는 것만으로 얻는 정보가 있습니다. 한 칸씩 가는 slow와 두 칸씩 가는 fast를 같이 출발시키면 fast가 끝에 닿는 순간 slow는 절반 지점에 있습니다.
def middle(head):
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
return slow.value
길이를 세고 절반까지 다시 가는 방법도 있지만 두 번 훑게 됩니다. 같은 방식으로 사슬이 자기 자신으로 되돌아오는 고리를 만들었는지도 잡아냅니다.
def has_cycle(head):
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
고리가 없으면 fast가 먼저 끝에 닿아 False가 나옵니다. 고리가 있으면 원형 트랙에서 빠른 사람이 느린 사람을 따라잡듯 두 포인터가 같은 노드에서 만납니다. 여기서 is는 값이 같은지가 아니라 같은 노드인지를 묻는 비교입니다.
8. 그래서 언제 쓰는가
연결 리스트는 인덱스 접근과 탐색이 O(n)으로 느린 대신 위치만 잡고 있으면 넣고 빼기가 O(1)인 자료구조입니다. 다만 직접 만들어 쓸 일은 많지 않습니다. 노드가 흩어져 있어 값 하나 읽을 때마다 먼 자리를 뒤져야 하고, 순회 속도는 값들이 붙어 있는 배열이 앞서는 경우가 많습니다.
그래도 익혀두는 이유는 자주 쓰는 도구의 속을 열면 이 구조가 들어 있기 때문입니다. 파이썬 deque와 해시 충돌 처리, 오래된 항목을 버리는 캐시가 모두 노드를 잇고 떼는 방식으로 동작합니다. 노드 몇 개를 손으로 그려 화살표를 옮겨보면 코드가 빨리 눈에 들어옵니다.