pointer rewiring

삭제는 노드를 지우기 전에 이웃 포인터를 먼저 다시 잇는 일이다

단일 연결 리스트는 삭제 대상의 이전 노드를 찾아 next를 건너뛰게 만들고, 이중 연결 리스트는 prev와 next를 양방향으로 재배선한다.

Singly linked list

이전 노드를 찾아 next 하나를 바꾼다

삭제 대상 X만 알고 있으면 부족하다. A를 찾아 A.next를 B로 바꾼다.

before

Anext X
→
X 삭제next B
→
Bnext ...

prev 역할을 할 A를 먼저 확보한다.

rewire A가 X를 건너뛰게 한다 prev.next = target.next

after

Anext B
→
Bnext ...
Xdetached

수정은 O(1)이지만 A를 찾는 준비가 O(N)일 수 있다.

Doubly linked list

대상 노드 기준으로 양쪽 포인터를 바꾼다

X.prev와 X.next를 알고 있으므로 A와 B를 즉시 서로 연결한다.

before

Aprev / next
⇄
X 삭제prev A · next B
⇄
Bprev / next

X가 양쪽 이웃을 이미 가리킨다.

rewire A와 B를 양방향으로 연결 X.prev.next = X.next X.next.prev = X.prev

after

Anext B
⇄
Bprev A
Xdetached

대상 노드를 이미 알고 있으면 포인터 두 개 수정으로 O(1)이다.

탐색 비용 값으로 대상을 찾는 과정은 둘 다 O(N)일 수 있지만, 단일 리스트는 삭제 직전 이전 노드가 반드시 필요하다.
수정 비용 단일은 next 하나, 이중은 prev와 next 둘을 바꾼다. 이중은 포인터가 더 많지만 대상 삭제가 직접적이다.