[자료구조 07] 연결 리스트, 노드를 사슬처럼 잇기

지금까지 본 파이썬 리스트는 값을 한 칸씩 붙여 놓은 좌석표에 가깝습니다. 자리에 번호가 매겨져 있어 몇 번째 값이든 바로 꺼낼 수 있지요. 연결 리스트(linked list, 이어 붙인 목록)는 생각이 조금 다릅니다. 값 하나하나가 "내 다음은 이 사람"이라는 화살표를 들고 손을 맞잡아 사슬처럼 이어진 구조입니다. 번호로 바로 찾지는 못하지만, 중간에 새 값을 끼워 넣는 일이 개념적으로 아주 간단합니다. 실무에서는 파이썬의 list와 deque로 대부분 해결되지만, 연결 리스트의 생각법은 자료구조의 기본기라 직접 만들어 보며 익혀 두면 좋습니다.

07.1 노드라는 작은 상자

연결 리스트의 재료는 노드(node, 마디)입니다. 노드 하나는 두 가지를 담습니다. 하나는 값(value)이고, 다른 하나는 다음 노드를 가리키는 화살표(next)입니다. 이 화살표가 다음 노드를 손가락으로 가리키는 셈이고, 그 연결이 이어지며 사슬이 됩니다. 마지막 노드는 더 가리킬 곳이 없으니 화살표가 None(없음)을 가리킵니다.

파이썬에서는 클래스(class, 설계도)로 노드를 만듭니다. 값과 화살표를 담을 상자를 하나 정의하는 것입니다. 클래스는 "이런 모양의 물건을 찍어 내는 틀"이라고 생각하면 됩니다. 이 틀로 노드를 여러 개 찍어 내고, 각 노드의 화살표를 서로 연결해 사슬을 만듭니다. 화살표가 가리키는 대상만 바꾸면 사슬의 순서가 통째로 바뀌는 것이 연결 리스트의 묘미입니다.

07.2 노드를 손으로 잇고 순회하기

노드 셋을 만들어 A → B → C로 이은 뒤, 처음부터 화살표를 따라가며 값을 모아 보겠습니다.

class Node:

def __init__(self, value):

self.value = value

self.next = None

a = Node("A"); b = Node("B"); c = Node("C")

a.next = b

b.next = c

cur = a

seq = []

while cur:

seq.append(cur.value)

cur = cur.next

print(seq)

['A', 'B', 'C']

__init__은 노드를 만들 때 값을 넣고 화살표(next)를 일단 None으로 두는 부분입니다. a.next = b는 A의 화살표가 B를 가리키게 하고, b.next = c는 B가 C를 가리키게 합니다. 이렇게 사슬이 완성됩니다.

아래쪽이 순회(traversal, 처음부터 끝까지 훑기)입니다. cur를 첫 노드 a에 두고, cur.value로 값을 담은 뒤 cur = cur.next로 다음 노드로 넘어갑니다. 마지막 노드 C의 next는 None이라 while cur가 거짓이 되어 멈춥니다. 노드 수만큼 따라가므로 순회는 O(n)입니다. 번호로 바로 못 가고 앞에서부터 짚어 가야 한다는 점이 파이썬 리스트와 크게 다릅니다.

07.3 맨 앞에 새 값을 끼우기

연결 리스트의 강점은 삽입입니다. 특히 맨 앞에 넣는 일이 아주 빠릅니다. 새 노드를 만들어 그 화살표를 기존 첫 노드로 돌리고, 시작점만 새 노드로 바꾸면 끝이기 때문입니다. head(머리, 첫 노드를 가리키는 표시)라는 이름으로 시작점을 관리해 보겠습니다.

class Node:

def __init__(self, value):

self.value = value

self.next = None

class LinkedList:

def __init__(self):

self.head = None

def push_front(self, v):

n = Node(v)

n.next = self.head

self.head = n

def to_list(self):

out = []; cur = self.head

while cur:

out.append(cur.value)

cur = cur.next

return out

ll = LinkedList()

for v in ["X", "Y", "Z"]:

ll.push_front(v)

print(ll.to_list())

['Z', 'Y', 'X']

push_front는 새 노드 n을 만들고 n.next = self.head로 새 노드가 기존 첫 노드를 가리키게 한 뒤, self.head = n으로 시작점을 새 노드로 옮깁니다. X, Y, Z를 차례로 앞에 끼웠더니 가장 나중에 넣은 Z가 맨 앞에 왔습니다. 화살표 두 개만 고치면 끝나므로 맨 앞 삽입은 O(1)입니다. 파이썬 리스트의 insert(0)이 뒤 값을 모두 밀어야 해서 O(n)인 것과 대비됩니다.

07.4 중간에 노드 끼우기

중간 삽입도 화살표만 바꾸면 됩니다. 앞의 A → B → C에서 B 뒤에 New를 넣어 보겠습니다.

newn = Node("New")

newn.next = b.next # New가 C를 가리키게

b.next = newn # B가 New를 가리키게

cur = a; seq = []

while cur:

seq.append(cur.value)

cur = cur.next

print(seq)

['A', 'B', 'New', 'C']

순서가 중요합니다. 먼저 newn.next = b.next로 New가 원래 B의 다음이던 C를 가리키게 하고, 그다음 b.next = newn으로 B가 New를 가리키게 합니다. 이 순서를 바꾸면 C로 가는 길을 잃어버립니다. 뒤에 있는 값들을 한 칸씩 밀 필요 없이 화살표 두 개만 고치면 되므로, 자리를 이미 알고 있을 때 삽입 자체는 O(1)입니다. 다만 그 자리를 찾아가는 데는 앞에서부터 짚어야 하므로 O(n)이 듭니다.

07.5 파이썬 리스트와 무엇이 다른가

둘의 성격을 나란히 두면 이렇습니다. 파이썬 리스트는 번호로 몇 번째 값이든 바로 꺼내는 O(1) 접근이 강점이지만, 앞이나 중간에 넣고 뺄 때는 뒤 값을 모두 밀어야 해서 O(n)입니다. 연결 리스트는 반대로 번호로 바로 가지 못해 특정 위치를 찾는 데 O(n)이 들지만, 자리만 알면 뒤 값을 건드리지 않고 화살표만 바꿔 삽입과 삭제를 O(1)에 합니다.

그래서 "번호로 자주 꺼내야 하면 리스트, 앞뒤로 자주 넣고 빼야 하면 이어 붙이는 구조"가 큰 기준입니다. 예를 들어 값을 죽 저장해 두고 몇 번째 값을 자주 조회한다면 리스트가 유리하고, 목록의 앞이나 중간에 계속 새 값을 끼워 넣어야 한다면 화살표만 고치는 연결 리스트의 방식이 어울립니다.

파이썬에서 앞뒤 삽입과 삭제가 잦다면 직접 만든 연결 리스트보다 이미 O(1)로 최적화된 deque를 쓰는 편이 실용적입니다. 그래서 연결 리스트를 실무에서 손수 구현할 일은 많지 않습니다. 그럼에도 노드가 서로를 가리키며 이어진다는 생각법은 트리(계층 구조)나 그래프(관계 구조) 같은 자료구조의 바탕이 되므로, 화살표로 잇는 감각을 익혀 두는 것이 중요합니다.

07.6 정리

연결 리스트는 값과 다음 노드를 가리키는 화살표를 가진 노드들이 사슬처럼 이어진 구조입니다. 번호로 바로 못 가 순회와 위치 찾기에 O(n)이 들지만, 자리만 알면 화살표만 바꿔 삽입과 삭제를 O(1)에 처리합니다. 파이썬 리스트의 강점(빠른 번호 접근)과 정확히 반대인 셈입니다. 노드 클래스를 직접 만들어 A, B, C를 잇고 중간에 값을 끼워 보면, 화살표가 어디를 가리키는지 손으로 따라가며 구조가 또렷해집니다.