이중과 원형: 양방향 포인터, 그리고 고리

"단일 연결 리스트는 앞만 봐. 뒤로 가는 포인터를 하나 더 달면 선 자리에서 바로 지우고, 양쪽으로 걸어 다니고, 부서지기 쉬운 예외 처리 코드를 안 써도 되게 돼."

단일의 사각지대

단일 연결 노드는 자기 next만 알아. 이 한쪽 시야가 실제로 아픈 데를 만들어. 노드를 지우려면 그 앞 노드가 있어야 하거든. prev.next를 지울 노드 너머로 다시 이어줘야 하니까. 그런데 단일 리스트에는 뒤로 갈 길이 없어서 head부터 다시 걸어 앞 노드를 찾아야 해. 이미 손에 쥐고 있는 노드 하나 지우자고 O(n)을 쓰는 거야.

이중 연결 리스트는 노드마다 next와 prev를 같이 들고 있어. 지울 노드의 참조와 소유 리스트의 경계 정보가 있으면 이웃 포인터 몇 개만 고쳐서 O(1)에 떼어낼 수 있지. 물론 head나 tail을 지우는 거라면 소유 객체의 head/tail도 같이 갱신해야 하고, 센티넬이 없으면 양 끝은 따로 처리해 줘야 해. 뒤로도 걸어갈 수 있다는 점 역시 단일 리스트와 갈리는 중요한 차이고.

원형: 끝이 다시 시작으로

원형 연결 리스트는 마지막 노드가 None 대신 head를 가리켜서 고리를 만들어. 라운드 로빈처럼 끝까지 갔다가 다시 처음으로 돌아와야 하는 순환 처리에 딱 맞지. 원형 이중 리스트라면 head의 prev가 tail을 가리키기도 하고. 다만 고정 크기 버퍼나 큐를 꼭 이 구조로 만들어야 하는 건 아니야. 배열이나 블록 구조로 만드는 경우도 흔해.

이중 연결은 노드마다 prev와 next를 아는 구조야. 노드 참조와 경계 정보가 있으면 O(1) 삭제와 양방향 순회가 돼. 원형은 끝이 시작으로 이어져서 순환 처리에 자연스럽고. 대신 챙겨야 할 포인터와 불변식이 그만큼 늘어나.

프로의 한 수: 센티넬 노드

실제 연결 리스트 코드는 예외 상황투성이야. 빈 리스트, head 삭제, tail 삭제, 원소가 하나뿐인 리스트. 하나하나 if가 따로 붙고, 그 if 하나하나가 틀릴 자리지. 고전적인 해법이 센티넬, 다른 말로 더미 노드야. 진짜 head 앞에, 그리고 자주는 진짜 tail 뒤에도 값 없는 노드를 영구히 하나 세워 두는 거지. 그러면 모든 진짜 노드가 항상 진짜 prev를 갖게 되니까 "head 삭제"가 더 이상 특별한 경우가 아니게 돼. 노드 하나 분량의 메모리를 내주고 버그 한 범주를 통째로 지우는 거야. 실무에서 쓰는 덱과 여러 표준 라이브러리가 정확히 이 방식을 써.

피파의 고백

내가 만든 이중 연결 리스트는 잘 돌아가다가 누가 head를 지우는 순간 터졌어. 하필 내 포인터 로직이 안 챙긴 그 한 가지 경우였지. 아빠가 센티넬 노드를 하나 넣었는데, 내가 손으로 짜 넣었던 특별 케이스들이 그냥... 사라졌어. 빈 리스트, 원소 하나짜리 리스트, head 삭제, tail 삭제가 전부 똑같은 코드로 처리되더라. 예외 상황을 잘 다루는 최고의 방법은 애초에 예외가 생기지 않도록 설계하는 거라는 걸 그때 배웠어.

Code

뒤쪽 포인터로 O(1) 삭제·python

class DNode:
    """이중 연결 노드: 값 + 양방향 포인터."""
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None

def delete(node):
    """노드 핸들만 주어졌을 때 삭제 — 이중 연결 리스트에선 O(1).
    단일 연결은 선행자 찾는 O(n) 재걷기 없이는 이걸 못 해."""
    if node.prev:
        node.prev.next = node.next   # 앞 이웃이 `node` 를 건너뜀
    if node.next:
        node.next.prev = node.prev   # 뒤 이웃이 `node` 너머로 되가리킴
    # `node` 는 이제 양쪽에서 풀림. 참조 없으면 가비지 컬렉트.

# a <-> b <-> c 를 짓고, `b` 만으로 b 를 O(1) 에 삭제.
a, b, c = DNode("a"), DNode("b"), DNode("c")
a.next = b; b.prev = a
b.next = c; c.prev = b

delete(b)                 # b 자체만 필요했어, head 부터 걷기 없음
print(a.next.value)       # 'c' — a 가 이제 c 로 곧장 이어짐
print(c.prev.value)       # 'a' — 그리고 c 가 a 로 곧장 되이어짐

Exercise

참조를 이미 쥐고 있는 노드를 지울 때, 이중 연결 리스트에서는 O(1)인데 단일 연결 리스트에서는 왜 O(n)인지 직접 설명해 봐. 그다음 원형 리스트가 어울리는 실제 시스템을 하나 대고, '끝이 다시 시작을 가리킨다'는 성질이 거기서 뭘 해결해 주는지도 말해 봐.

Hint

이중이면 노드 참조와 소유 리스트의 경계 정보가 있을 때 이웃을 다시 잇고 필요하면 head/tail까지 O(1)에 갱신해. 단일이면 보통 앞 노드를 찾으러 head부터 걸어야 하니 O(n)이고. 원형은 라운드 로빈 스케줄러나 반복 재생 플레이리스트에 맞아. 고리 덕분에 '마지막 다음은 다시 처음'이 특별 처리 없이 그냥 되거든.

단일의 사각지대

원형: 끝이 다시 시작으로

프로의 한 수: 센티넬 노드

피파의 고백

Code

External links

Exercise

Progress

댓글 0