삭제 경로

이전 노드 확보와 삭제 비용

단일 리스트는 next만 있어 이전 노드를 탐색하고, 이중 리스트는 prev와 next를 함께 재배선한다.

단일 연결 리스트

삭제 대상만 알아서는 부족하다. head부터 걸어와 이전 노드를 찾아야 한다.

10next -> 20
20next -> 30
30 삭제next -> 40
1. 이전 탐색20을 찾을 때까지 O(N) 순회
2. 링크 교체20.next = 30.next
3. 비용 해석수정은 O(1), 준비가 O(N)

이중 연결 리스트

삭제 대상 노드가 prev와 next를 알고 있어 양쪽 이웃을 바로 잇는다.

20prev/next
30 삭제prev/next
40prev/next
1. 대상 확보노드를 이미 알면 이전 탐색 생략
2. 재배선20.next = 40, 40.prev = 20
3. 비용 해석링크 두 개 수정으로 O(1)
탐색 비용 두 구조 모두 값을 찾아야 하면 O(N)이지만, 단일 리스트는 삭제 직전 이전 노드까지 필요하다.
수정 비용 단일은 next 하나, 이중은 prev와 next 둘을 바꾼다. 이중은 수정 항목이 많지만 대상 노드 삭제가 직접적이다.