Circular Linked List
A circular linked list is a linked list in which the last node's next pointer does not hold null but instead points back to the first node, forming a close...
Ring-Structured Lists Where the Last Node Points to the First
A circular linked list is a linked list in which the last node's next pointer does not hold null but instead points back to the first node, forming a closed ring. Circular lists come in singly circular and doubly circular variants, combining the properties of their non-circular counterparts with the wrap-around connection.
The primary motivation for circular lists is to model cyclic structures directly. A round-robin task scheduler that cycles through processes indefinitely is a natural fit: the scheduler holds a pointer to the current process, executes it for a time slice, and advances the pointer to next, which wraps around without any boundary check. There is no special case for reaching the end.
Traversal of a circular linked list cannot use the null pointer as a stopping condition because no node has a null next. Instead, traversal starts from a designated starting node (often head or a cursor pointer) and loops until the starting node is reached again. The loop condition is: continue while current.next is not equal to start. This requires saving the starting node before the loop begins.
Insertion at any position maintains the circular property: after adjusting next pointers, verify that the last node still points to the first node. This invariant must be preserved by every modification operation. Inserting before the head requires traversing to the last node to update its next pointer to the new node.
One elegant advantage of a doubly circular list is that you can reach both the head and tail from any single pointer. Given a pointer to any node, the previous node is node.prev and the head can be found by following prev pointers around (though this would be O(n)). In practice, a pointer to the tail gives O(1) access to both the tail (directly) and the head (via tail.next), which is why many circular list implementations keep a tail pointer rather than a head pointer.
Real-world applications include the Josephus problem (a counting-out game modeled as a circular list), circular buffers in networking and audio processing, and multiplayer board game systems where turn order wraps around.
Worked example: Josephus problem with n people and every k-th person eliminated. Represent people as nodes in a circular singly linked list. Starting from the first node, advance k-1 steps, remove the k-th person by adjusting the predecessor's next pointer, and repeat until one node remains. The simulation runs in O(n times k) time.
Interview tip: detecting whether a singly linked list is actually circular (an unintended cycle) is a different problem, solved by Floyd's algorithm. Distinguish clearly between intentionally circular lists and unintentional cycles in your explanations.