5 / 14강

연결 리스트

보물찾기 쪽지마다 다음 쪽지의 위치가 적혀 있다고 생각해 보세요. 쪽지들이 나란히 놓여 있을 필요는 없습니다. 연결 리스트는 각 항목이 다음 항목을 가리키는 구조입니다.

노드와 첫 번째 항목

• 노드(node): 값과 다음 노드의 참조를 묶은 항목입니다.
• 헤드(head): 첫 번째 노드를 가리킵니다. 여기서부터 연결을 따라갑니다.
• 끝: 다음 노드가 없다는 것을 None으로 표시합니다.

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

head = Node("A", Node("C"))
head.next = Node("B", head.next)

current = head
while current is not None:
    print(current.value)
    current = current.next

출력은 A, B, C입니다. class는 노드의 틀을 만들고, self.value와 self.next는 각 노드가 기억할 값입니다.

삽입할 때 바뀌는 것

처음에는 A → C → None입니다. 새 노드 B가 C를 가리키게 한 다음, A가 B를 가리키게 바꾸면 A → B → C → None이 됩니다. C를 다른 메모리 칸으로 밀 필요는 없습니다.

순서가 중요합니다. 기존 다음 노드의 참조를 잃기 전에 새 노드에 연결해야 합니다. 삭제할 때는 이전 노드가 삭제 대상의 다음 노드를 가리키도록 바꿉니다.

삽입은 언제 빠를까요?

삽입할 위치의 이전 노드를 이미 알고 있다면 연결을 바꾸는 일은 O(1)입니다. 하지만 ‘다섯 번째 위치’를 먼저 찾아야 한다면 헤드부터 걸어가야 합니다. 위치 탐색은 최악에 O(n)입니다.

연결 리스트는 다음 노드를 기억할 공간도 필요합니다. 배열은 인덱스로 바로 접근하고, 연결 리스트는 연결을 따라갑니다. ‘삽입이 많으면 무조건 연결 리스트’처럼 외우기보다 위치를 어떻게 찾는지도 따져 보세요.

확인 문제

A → B → C에서 B를 지우려 합니다. A를 이미 알고 있다면 어떤 연결을 바꾸면 될까요? head만 알고 B를 값으로 찾아 지운다면 전체 비용은 늘어날까요?