노드와 포인터: 사슬 짓기

"배열은 한 거리에 늘어선 집들이야. 연결 리스트는 보물찾기야: 각 단서가 상품이랑 다음 단서의 위치를 들고 있어. 단서 없으면, 앞으로 갈 길도 없어."

노드가 아이디어 전부야

연결 리스트는 노드로 지어지고, 노드는 거의 모욕적일 만큼 단순해: 두 가지를 담은 작은 상자 — 값, 그리고 다음 노드를 가리키는 포인터. 그게 다야. 여럿을 엮어 — 각자 다음을 가리키며 — 마지막은 아무것도 안 가리켜 (None), 끝을 표시해. 첫 노드, 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 를 나머지로 되돌리기 전에 new_node = 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