Circular Linked Lists

Analogy categoryAnalogies

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

python

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 = 0

Explanation

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

python

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 circular

Complexity

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?

Doubly Linked Lists

Linked List Operations and Problems

Topics covered

#Python#DataStructuresStudyNotes#DataStructures#CircularLinkedLists#Circular#Linked#Lists#Structure#StudyNotes#SkillVeris