정의

이중 연결 리스트(Doubly Linked List)는 각 노드가 데이터와 함께 이전 노드를 가리키는 prev, 다음 노드를 가리키는 next 두 개의 포인터를 가진 자료구조입니다. 단일 연결 리스트가 한 방향(next)으로만 이동할 수 있는 것과 달리, 양방향으로 순회할 수 있습니다.

핵심 특성

• ✓양방향 포인터: 각 노드는 [prev | 데이터 | next]로 구성되어 앞뒤로 이동할 수 있습니다.
• ✓역방향 순회: tail에서 prev를 따라 거꾸로 탐색할 수 있습니다. 단일 연결로는 불가능합니다.
• ✓O(1) 삭제: 삭제할 노드의 참조가 있으면, 그 노드의 prev/next로 양옆을 바로 이어 O(1)에 삭제합니다.
• ✓추가 메모리: 노드마다 prev 포인터가 더 필요해 단일 연결보다 메모리를 약간 더 씁니다.

시간 복잡도