dummy가 닫는 양방향 고리
노드 수를 바꾸면 dummy.next와 dummy.prev가 가리키는 대상이 달라진다. 빈 목록에서는 두 참조가 모두 dummy 자신을 가리킨다.
현재 상태
dummy.next
dummy.prev
n
센티널이 값을 대신 저장하는 것은 아니다. 첫 노드의 앞과 마지막 노드의 뒤를 맡아 양끝에서도 참조가 비지 않게 한다.
경계에서도 같은 연결 규칙 쓰기
연산 위치를 바꾸어도 삽입은 새 노드와 양옆 노드의 참조 네 개를, 삭제는 양옆 노드의 참조 두 개를 바꾼다. dummy가 실제 노드의 자리를 대신할 수 있다.
현재 상태
참조 변경 단계
첫 자리와 마지막 자리, 빈 목록은 여전히 경계다. dummy가 이 자리에서 필요한 이웃 노드를 제공하므로 별도의 head·tail 갱신 분기가 사라진다.
가까운 끝에서 i번째 노드 찾기
앞 절반은 dummy.next에서 next를 따라가고, 뒤 절반은 dummy에서 prev를 따라간다.
현재 상태
찾을 위치
가까운 끝을 선택하면 이동 횟수는 min(i, n − i)이다. 따라서 i번째 노드를 찾는 비용은 Θ(1 + min{i, n − i})이다.