Data Structures
Circular Linked List
Difficulty: Intermediate
An operating system rotating turns among four CPU-bound processes, a music player on shuffle-repeat, and the classic Josephus problem all share the same shape: a finite list of items consulted in cyclical order, where 'after the last'...
Circular Linked List
An operating system rotating turns among four CPU-bound processes, a music player on shuffle-repeat, and the classic Josephus problem all share the same shape: a finite list of items consulted in cyclical order, where 'after the last' means 'back to the first'. A Circular Linked List encodes that shape directly, with the last node's next pointer wired to the head instead of null.
This lesson covers the circular singly linked list and its doubly linked variant, the stop condition for traversal (return to the starting node rather than waiting for null), insertion at the head and at the tail in O(1) when a tail pointer is maintained, and deletion that correctly handles the wrap-around. You will also compare circular structures with the standard linear forms so you know when bending the list back on itself is the right call and when it just complicates traversal.
In Linked Lists (Singly), traversal terminated when you reached a null next pointer; here, the same loop must compare against the starting node instead, a small change that exposes the distinction between cycle detection and cycle definition (Floyd's tortoise-and-hare reuses this idea later).
With all three linked-list shapes covered, the curriculum next pivots to tree-based and array-based structures with stronger time guarantees.
Prerequisites:
Linked Lists (Singly)Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Describe the circular singly linked list structure and explain how it differs from a standard singly linked list.
Describe the circular doubly linked list structure where last.next = head and head.prev = last.
Implement insertion at head, at tail (O(1) with a tail pointer), and after a given node in both JavaScript and Python.
Implement deletion by value with correct circular wrap-around handling in both JavaScript and Python.
Traverse a circular linked list by detecting the cycle (stop when back at head) and analyze time complexity of all operations.
Apply circular linked lists to real-world problems including round-robin scheduling, circular buffers, and the Josephus problem.
Why This Matters
01
Circular linked lists model naturally cyclic systems such as round-robin CPU scheduling, turn-based game rotation, and circular buffers, making them a practical data structure for OS and systems programming.
02
The Josephus problem is a classic interview and competitive-programming question that is most elegantly solved with a circular linked list, demonstrating how the right data structure simplifies an otherwise complex problem.
03
Understanding circular traversal and the stop condition (returning to the starting node) teaches a key pointer-manipulation skill that transfers directly to cycle detection algorithms like Floyd's tortoise-and-hare.
04
Comparing circular, singly, and doubly linked lists deepens your understanding of pointer-based structures and helps you choose the optimal variant for each problem context.
Key Terms
6 terms you'll encounter in this lesson
Circular linked list
A linked list where the last node's next pointer points back to the head node instead of null, forming a continuous loop.
Tail pointer
A reference to the last node in the list. In a circular list, tail.next always equals head, enabling O(1) access to both ends.
Circular traversal
Walking through the list by following next pointers until you arrive back at the starting node. The stop condition is current === start (not current === null).
Circular doubly linked list
A circular list where each node has both next and prev pointers. The head's prev points to the tail, and the tail's next points to the head.
Round-robin scheduling
A scheduling algorithm that cycles through processes in a fixed order, giving each a time slice. A circular linked list models the process queue naturally.
Josephus problem
A classic counting-out problem where n people stand in a circle and every k-th person is eliminated until one remains. Solved elegantly with a circular linked list.
Heads Up
Common misconceptions to watch out for
"A circular linked list causes an infinite loop during traversal"
Only if you use the wrong stop condition. In a linear list you stop at null; in a circular list you stop when you return to the starting node. The traversal is always O(n) -- you visit each node exactly once.
"You need both head and tail pointers for O(1) insertion at both ends"
With a circular singly linked list you only need a tail pointer. Since tail.next is head, you have O(1) access to the head through the tail. Inserting at head means inserting after tail and updating tail.next.
"Circular lists are always singly linked"
Circular lists can be singly or doubly linked. A circular doubly linked list has head.prev = tail and tail.next = head, enabling O(1) bidirectional traversal and O(1) deletion by reference.
"Deleting from a circular list works the same as a linear list"
Deletion requires special handling when the list has only one node (self-loop), when deleting the head (update tail.next), or when deleting the tail (update the new last node's next to head). The circular invariant must be maintained at all times.