Introduction
A circular linked list is a linked list in which the last node's next pointer references the first node instead of None, forming a closed loop. This can be built from either a singly linked list (one-directional loop) or a doubly linked list (loop in both directions). Circular linked lists are useful for applications that need to cycle through elements repeatedly, such as round-robin scheduling or a circular buffer of players in a turn-based game.
Cricket analogy: A fielding rotation where the last fielder's "next" position loops back to the first, instead of ending, models how captains cycle part-time bowlers through overs in a round-robin, rather than a straight batting order that simply ends.
Structure/Syntax
class CNode:
def __init__(self, value):
self.value = value
self.next = None
class CircularLinkedList:
def __init__(self):
self.tail = None # tail.next always points to head
self.size = 0Explanation
It is common to track only a tail reference in a circular linked list, since the head is always available as tail.next. Traversal must use an explicit stopping condition (such as counting nodes or checking for a return to the starting node) instead of checking for None, because no node's next pointer is ever None. Care must be taken to avoid infinite loops when writing traversal code.
Cricket analogy: A captain tracking only "who bowled the last over" can always find "who bowls next" from that reference, but counting overs bowled needs an explicit stop condition (reaching the target over count) since the bowling rotation never naturally runs out like a fixed XI.
Example
class CNode:
def __init__(self, value):
self.value = value
self.next = None
class CircularLinkedList:
def __init__(self):
self.tail = None
self.size = 0
def append(self, value):
node = CNode(value)
if self.tail is None:
node.next = node
self.tail = node
else:
node.next = self.tail.next
self.tail.next = node
self.tail = node
self.size += 1
def to_list(self):
result = []
if self.tail is None:
return result
head = self.tail.next
current = head
while True:
result.append(current.value)
current = current.next
if current is head:
break
return result
cll = CircularLinkedList()
for v in [1, 2, 3, 4]:
cll.append(v)
print(cll.to_list())
print(cll.tail.next.value) # head value, since it's circularComplexity
append is O(1) when a tail reference is maintained, since the new node is inserted right after the tail and becomes the new tail. Traversing the full list is O(n), same as a linear linked list, but the loop must terminate on a condition like 'returned to the starting node' rather than hitting None. Searching for a value is O(n) in the worst case.
Cricket analogy: Adding a new bowler to the end of a fixed bowling rotation is instant since you just link them after the current last bowler, but confirming everyone's bowled requires walking the whole rotation until you're back at the first bowler, and finding a specific bowler's spot takes a full pass in the worst case.
Key Takeaways
- The last node's next pointer references the first node instead of None, forming a loop.
- Tracking just a tail pointer is enough, since head is always tail.next.
- Traversal must use a stopping condition (like returning to the starting node) instead of checking for None.
- Circular linked lists are well suited for round-robin scheduling and cyclic buffers.
- Both singly and doubly linked variants of circular lists exist.
Practice what you learned
1. What distinguishes a circular linked list from a standard singly linked list?
2. Why is it sufficient to store only a tail reference in the CircularLinkedList example?
3. What is a real-world use case well suited to circular linked lists?
4. What must traversal code for a circular linked list avoid checking, unlike a standard linked list?
Was this page helpful?
You May Also Like
Singly Linked Lists
A linear data structure of nodes connected one-way by next pointers, enabling O(1) head insertion.
Doubly Linked Lists
A linked list where each node has both next and previous pointers, allowing efficient bidirectional traversal.
Circular Queues
A fixed-size queue that reuses freed slots by wrapping indices with the modulo operator, avoiding wasted space.
Linked List Operations and Problems
Classic linked list algorithms including reversal, cycle detection with Floyd's algorithm, and finding the middle node.