이중 연결 리스트란?
이중 연결 리스트(Doubly Linked List)는 각 노드가 데이터와 함께 이전 노드를 가리키는 prev, 다음 노드를 가리키는 next 두 개의 포인터를 가진 자료구조입니다.
단일 연결 리스트가 next 하나로 한 방향으로만 이동할 수 있는 것과 달리, 이중 연결 리스트는 앞뒤 양방향으로 자유롭게 순회할 수 있습니다. 음악 플레이어의 이전 곡/다음 곡, 브라우저의 뒤로/앞으로 가기가 모두 이 구조의 응용입니다.
단일 연결 리스트와 무엇이 다른가?
| 항목 | 단일 연결 | 이중 연결 |
|---|---|---|
| 포인터 | next만 | prev + next |
| 순회 방향 | 앞으로만 | 앞/뒤 모두 |
| 노드 삭제 | 이전 노드를 따로 찾아야 함 | 노드 참조만 있으면 O(1) |
| 메모리 | 적음 | prev만큼 더 사용 |
핵심 차이는 두 가지입니다.
- •역방향 순회: tail에서 prev를 따라 거꾸로 탐색할 수 있습니다. 단일 연결로는 불가능합니다.
- •O(1) 삭제: 삭제할 노드의 참조만 있으면, 그 노드의 prev/next로 양옆을 바로 이어 탐색 없이 삭제합니다.
핵심 접근법
이중 연결 리스트를 다룰 때 절대 잊으면 안 되는 원칙이 하나 있습니다. 연결을 바꿀 때는 항상 양쪽 포인터를 짝으로 갱신한다.
- •앞/뒤 추가: 새 노드의 prev/next를 끝 노드에 연결하고, 끝 노드의 포인터도 새 노드를 가리키게 합니다.
- •중간 삽입: 앞 노드의 next, 뒤 노드의 prev, 새 노드의 prev/next까지 총 4개 포인터를 갱신합니다.
- •삭제:
node.prev.next = node.next,node.next.prev = node.prev로 양옆을 서로 이어 한 노드를 우회합니다.
한쪽만 바꾸면 반대 방향 링크가 끊어져 순회가 깨지므로, "양쪽을 짝으로"가 가장 중요한 감각입니다.
알고노트에서 직접 확인하세요
prev/next 양방향 화살표가 추가·삭제마다 어떻게 갱신되는지, 그리고 tail에서 시작하는 역방향 탐색이 어떻게 동작하는지 알고노트에서 한 스텝씩 시각적으로 확인할 수 있습니다.