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

"단일 연결 리스트는 앞만 봐. 뒤쪽 포인터를 더하면 갑자기 선 자리에서 삭제하고, 양방향으로 걷고, 깨지기 쉬운 엣지 케이스 코드를 그만 쓰게 돼."

단일의 사각지대

단일 연결 노드는 자기 next 만 알아. 그 외눈 시야가 진짜 고통을 일으켜: 노드를 삭제하려면 그 선행자가 필요해 (prev.next 를 그 노드 너머로 다시 잇게) — 근데 단일 리스트는 돌아갈 길을 안 줘서, head 부터 다시 걸어 선행자를 찾아야 해. O(n), 말 그대로 손에 쥔 노드 하나 삭제하려고.

이중 연결 리스트가 이걸 고쳐, 모든 노드에 포인터 둘을 줘서: next 그리고 prev. 이제 어떤 노드든, 두 이웃에 즉시 닿아 — 그래서 삭제가 O(1): node.prev.next 를 node.next 로, node.next.prev 를 node.prev 로 가리켜. 리스트를 뒤로도 걸을 수 있어, 단일 리스트는 그냥 못 하는 거.

원형: 끝이 시작으로 고리

원형 연결 리스트는 마지막 노드를 (None 대신) head 로 되돌려 가리켜, 고리를 이뤄. 순환하는 뭐든에 완벽해: 라운드 로빈 스케줄링 (각 작업에 차례를 줘, 영원히), 반복 재생 음악 플레이리스트, 스트리밍 데이터용 고정 크기 링 버퍼. 원형 이중 연결 리스트 — head.prev 가 tail 인 — 는 존재하는 가장 유연한 구조 중 하나고, 많은 실제 큐 구현을 굴리는 게 정확히 이거야.

이중 연결 = 각 노드가 prev 와 next 를 앎: 양방향 순회와 노드 주어졌을 때 O(1) 삭제. 원형 = 끝이 고리로 이어짐, 라운드 로빈과 버퍼에 이상적. 비용은 두 배 포인터와 연산당 두 배 장부 관리.

프로의 한 수: 센티넬 노드

실제 연결 리스트 코드는 엣지 케이스 투성이야: 빈 리스트, head 삭제, tail 삭제, 원소 하나짜리. 각각 특별한 if 가 필요하고, 각 if 가 틀릴 자리야. 고전적 고침은 센티넬 (또는 "더미") 노드 — 진짜 head 앞에 (그리고 종종 진짜 tail 뒤에) 앉는 영구적이고 값 없는 노드. 이제 "head 삭제" 특별 케이스가 없어, 모든 진짜 노드가 늘 진짜 prev 를 가지니까. 센티넬은 노드 하나 메모리를 들이고 버그 한 범주 전체를 지워. production 덱이랑 많은 표준 라이브러리가 하는 게 정확히 이거야.

피파의 고백

내 이중 연결 리스트는 완벽히 돌다가 누가 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

이중: prev 와 next 가 있어 두 이웃을 즉시 다시 이어. 단일: 선행자 찾으려 head 부터 걸어야 해 (O(n)). 원형은 라운드 로빈 스케줄러 / 반복 플레이리스트에 맞아 — 고리는 '마지막 다음은 자연스레 첫째로' 를 특별-케이스 리셋 없이 줘.

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

단일의 사각지대

원형: 끝이 시작으로 고리

프로의 한 수: 센티넬 노드

피파의 고백

Code

External links

Exercise

Progress

댓글 0