Circular Doubly Linked List

A Circular Doubly Linked List extends a standard linked list to allow efficient insertion, deletion, and traversal in both directions.

Its circular structure removes edge cases at the ends, making it ideal for complex data structures like heaps or graphs, where nodes frequently move between lists or are concatenated.

Structural Overview

Each node in a Circular Doubly Linked List contains:

• value — The data stored in the node
• prev — A pointer to the previous node in the list
• next — A pointer to the next node in the list

The list forms a loop, enabling continuous traversal without null references, therefore, the first nodes prev pointer, links to the last node, and the last nodes next pointer, links to the first node.

Additionally, typically, only a head pointer is maintained since any node is reachable from any starting point.

Operations & Implementation Details

The circular, symmetric design simplifies many operations, often achieving $O(1)$ time via pointer manipulation. These operations proceed smoothly, with only slight edge cases like empty lists or updating head pointers.

Insertion of a Value After Any Node

• The new_node bi-directionally points to the next_node of ref_node
• The ref_node bi-directionally points to the new_node
• Assign head pointers if the list was empty before insertion

Deletion Of A Node x

• The node previous to x bi-directionally points to the node after x
• Reassign head pointers for when head/tail is removed

Concatenation Of Two CDLLs A and B

• Connect the tail of A to the head of B bi-directionally
• Connect the tail of B to the head of A bi-directionally.