노드와 포인터: 사슬 엮기

"배열이 한 거리에 죽 늘어선 집이라면, 연결 리스트는 보물찾기야. 단서마다 상품 하나와 다음 단서가 있는 곳이 적혀 있지. 단서를 놓치는 순간 더 갈 데가 없어지고."

노드 하나면 설명이 끝나

연결 리스트는 노드를 엮어서 만들고, 노드는 허무할 만큼 단순해. 값 하나와 다음 노드를 가리키는 포인터 하나가 든 작은 상자, 그게 노드야. 이걸 여러 개 이어 붙이는데 각자 자기 다음을 가리키고, 맨 마지막 노드만 아무것도 안 가리켜(None). 그게 끝이라는 표시고. 첫 노드를 head라고 부르는데, head만 쥐고 있으면 next 포인터를 따라가서 사슬 전체에 닿을 수 있어.

Python에는 날것 포인터가 없지만 객체 참조가 똑같은 일을 해. node.next는 메모리 어딘가 다른 자리에 있는 노드 객체를 참조하지. 여기서 중요한 말이 "어딘가 다른 자리"야. 배열과 달리 노드들은 서로 옆에 붙어 있지 않아. 흩어진 채로 오직 참조로만 이어져 있어.

뭐가 싸고 뭐가 비싼가

"흩어진 상자를 포인터로 엮었다"는 그림에서 비용이 그대로 나와.

앞에 붙이기(새 head 추가)는 O(1). 노드를 새로 만들어 예전 head를 가리키게 하고, 그걸 새 head라고 부르면 끝이야. 나머지는 손도 안 대. 배열의 앞 삽입이 O(n)이었던 걸 떠올려 봐.
i번째 원소 접근은 O(n). 주소 계산 같은 건 없고, head부터 포인터를 i번 따라 걸어야 해.
값 검색도 O(n). 걸어가면서 하나씩 비교하는 수밖에 없어.
끝에 붙이기는 O(n). 단, tail 포인터를 따로 들고 있으면 O(1)이 돼.

노드는 (값, next 포인터) 한 쌍일 뿐이고, 연결 리스트는 head 참조에 노드 사슬이 달린 구조야. 앞에 붙이는 건 O(1). i번째 노드에 닿으려면 사슬을 걸어야 하니 O(n).

head를 잃으면 전부를 잃어

여기엔 만만히 보면 안 되는 약점이 하나 있어. head 참조가 유일한 입구라는 거. 기존 값을 어디 저장해두지 않고 덮어써 버리면 사슬 전체에 닿을 길이 사라져. 그러면 Python의 가비지 컬렉터가 조용히 노드를 전부 회수하고 데이터도 같이 없어지지. 연결 리스트 버그의 절반은 포인터를 잘못된 순서로 다시 할당해서 사슬을 끊어 먹는 거야. 리스트를 손볼 때는 포인터를 어떤 순서로 다시 잇느냐가 승부를 갈라.

피파의 고백

처음 짠 연결 리스트 삽입은 리스트 절반을 날려 먹었어. new_node.next를 나머지 사슬에 걸어두기도 전에 head 쪽 next부터 바꿔버린 거야. 순서가 뒤집힌 거지. 그 바람에 뒷부분이 통째로 가비지 컬렉터에게 떠내려갔어. 그때 아빠가 준 규칙을 지금도 손대기 전마다 속으로 외워. "옛 포인터를 돌리기 전에 새 노드의 next 를 먼저 걸어." 연결 리스트에서 순서는 사소한 디테일이 아니야. 리스트가 남느냐 누수가 나느냐가 거기서 갈려.

Code

노드, 그리고 단일 연결 리스트·python

class Node:
    """상자: 값, 그리고 다음 상자 참조 (끝이면 None)."""
    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt

class LinkedList:
    def __init__(self):
        self.head = None        # 유일한 입구. 잃으면 리스트를 잃어

    def prepend(self, value):           # 앞에 추가: O(1)
        self.head = Node(value, self.head)   # 새 노드가 옛 head 를 가리킴

    def traverse(self):                 # 모든 노드 방문: O(n)
        node = self.head
        while node is not None:
            print(node.value, end=" -> ")
            node = node.next            # 다음 상자로 포인터 따라가
        print("None")

    def find(self, value):              # 검색: O(n)
        node = self.head
        while node is not None:
            if node.value == value:
                return True
            node = node.next
        return False

ll = LinkedList()
for x in [3, 2, 1]:
    ll.prepend(x)        # 각 prepend 가 O(1)
ll.traverse()           # 1 -> 2 -> 3 -> None
print(ll.find(2))       # True (O(n) 걷기 후)

Exercise

위의 Node 클래스로 직접 손으로 따라가 봐. head -> A -> B -> C -> None이 있고 A 바로 뒤에 X를 넣고 싶어. 포인터 할당 두 줄을 올바른 순서로 써 봐. 순서를 뒤집으면 뭐가 잘못될까?

Hint

먼저 X.next = A.next로 X가 B를 가리키게 해. 그다음에 A.next = X. 순서를 뒤집으면 X가 아직 B를 모르는 상태에서 A.next = X가 먼저 실행돼. 그 순간 B와 C에 닿을 길이 사라지고 그대로 잃어버려.

노드 하나면 설명이 끝나

뭐가 싸고 뭐가 비싼가

head를 잃으면 전부를 잃어

피파의 고백

Code

External links

Exercise

Progress

댓글 0