6 / 14강

원형과 이중 연결 리스트

재생 목록에서 마지막 곡 다음에 첫 곡을 틀고 싶다면 끝을 처음에 연결하면 됩니다. 이전 곡으로도 바로 가려면 반대 방향의 연결을 하나 더 둡니다. 노드에 어떤 연결을 저장하느냐에 따라 가능한 이동이 달라집니다.

원형 연결 리스트

마지막 노드의 다음 참조가 첫 노드로 이어집니다. A → B → C → A처럼 순환합니다. 차례가 돌아오는 게임이나 반복 재생을 표현하기 좋습니다.

끝의 None을 기다리는 반복문은 멈추지 않습니다. 출발한 노드로 돌아왔는지 확인하거나, 이동 횟수를 정해야 합니다. 빈 리스트인지 확인하는 일도 필요합니다.

이중 연결 리스트

각 노드가 next뿐 아니라 prev도 기억합니다. A ↔ B ↔ C에서 B는 양옆 노드에 바로 접근합니다. 대신 참조를 저장할 공간이 더 들고, 삽입과 삭제 때 양방향 연결을 모두 맞춰야 합니다.

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

a, b, c = Node("A"), Node("B"), Node("C")
a.next, b.prev = b, a
b.next, c.prev = c, b

# Remove the middle node B.
a.next = c
c.prev = a
b.prev = b.next = None

print(a.next.value)
print(c.prev.value)

출력은 C, A입니다. A에서 앞으로 가도, C에서 뒤로 가도 연결이 맞습니다. B의 연결도 끊어, 이제 목록에 속하지 않는다는 상태를 분명히 했습니다.

구현에서 놓치기 쉬운 경우

• 첫 노드를 지우면 head를 갱신해야 합니다.
• 마지막 노드를 별도로 기억한다면 삭제 시 그 참조도 갱신해야 합니다.
• 원형 리스트에서 노드가 하나뿐이면 그 노드가 자신을 가리킵니다.
• Python의 메모리 회수는 런타임이 처리하지만, 끊거나 바꿔야 할 연결은 작성자가 맞춰야 합니다.

확인 문제

위 예제에서 a.next = c만 실행하고 c.prev = a를 빠뜨리면 어떤 문제가 생길까요?