Circular linked list
mediumNo null terminator, so every traversal needs a different stop condition - walk until you return to where you started. Forget that and you loop forever.
O(1) insertWorst O(n) searchSpace O(n)What to notice
The tail points back to the head
There is no null terminator, so every traversal needs a different stop condition: walk until you return to where you started. Forget that and you loop forever - the single most common bug with this structure.
Natural fit for round-robin
Turn-taking, CPU scheduling, a music playlist on repeat - anything that cycles endlessly through a fixed set. Advancing to 'the next one' is a single pointer hop with no wrap-around check.
Saved in this browser - no sign-up, nothing sent anywhere.
How a circular linked list works
Point the tail's next back at the head and the null terminator disappears. That one change turns a line into a ring: from any node, following next forever just cycles through the same elements. Nothing about the nodes themselves changed - same value, same single pointer - only the shape of the walk did.
Every traversal now needs a different stop condition. There is no null to hit, so you record where you started and walk until you come back. Forget that and a search for a missing value spins forever - the single most common bug with this structure.
The ring earns its keep wherever turn-taking never ends: round-robin CPU scheduling, a playlist on repeat, players around a table. Advancing to the next participant is one pointer hop with no wrap-around check, because the wrap is built into the structure instead of into every call site.
Step by step
- Build 12, 37, 5, 84 where 84's next points back at 12. head marks 12; no pointer anywhere in the ring is null.
- insertHead(9): point 9 at 12, move head to 9, and rewire 84's next to 9 so the ring stays closed.
- search(5): hop 9, 12, 37, and reach 5 on the fourth node - the same walk as any list.
- search(99): compare all five nodes, then stop the moment the walk returns to 9. Arriving back at your starting node is the only terminator.
- deleteHead: move head to 12 and point 84 at 12 - two writes and the ring is whole again.
- Cycle round-robin from 84: next is simply 12. No end-of-list check anywhere, which is the structure's entire appeal.
Complexity
| Best case time | O(1) insert |
|---|---|
| Worst case time | O(n) search |
| Space | O(n) |
Reference implementation
Python
class Node:
def __init__(self, value):
self.value = value
self.next = None
class CircularList:
def __init__(self):
self.head = None
def insert_head(self, v):
n = Node(v)
if not self.head:
n.next = n # a lone node points at itself
else:
last = self.head
while last.next is not self.head: # never None in a ring
last = last.next
n.next = self.head
last.next = n # keep the ring closed
self.head = n # O(n) here, O(1) with a tail pointer
def insert_tail(self, v):
self.insert_head(v) # same ring position as a head insert -
self.head = self.head.next # only the head pointer differs
def search(self, v):
if not self.head:
return -1
cur, i = self.head, 0
while True:
if cur.value == v:
return i
cur, i = cur.next, i + 1
if cur is self.head: # a full lap - v is absent
return -1JavaScript
class Node {
constructor(value) { this.value = value; this.next = null; }
}
class CircularList {
head = null;
insertHead(v) {
const n = new Node(v);
if (!this.head) {
n.next = n; // a lone node points at itself
} else {
let last = this.head;
while (last.next !== this.head) last = last.next; // never null
n.next = this.head;
last.next = n; // keep the ring closed
}
this.head = n;
}
search(v) {
if (!this.head) return -1;
let cur = this.head, i = 0;
do { // stop on a full lap, not on null
if (cur.value === v) return i;
cur = cur.next; i++;
} while (cur !== this.head);
return -1;
}
}Common pitfalls
- Looping forever on a failed search - the walk must compare against its starting node, because no null will ever stop it.
- Inserting at the head without re-pointing the tail: the ring closes past the new node, and a walk waiting to return to its start never does.
- Off-by-one in the one-node case: a single-node ring points at itself, and code assuming head differs from tail breaks on it.
- Computing length by walking to null: in a ring, size must be counted during exactly one full lap, or kept as a counter.
Where it is used
- Round-robin schedulers - each process's turn ends with a single next hop, no wrap logic.
- Media playlists on repeat, where after the last track comes the first.
- Turn order in multiplayer games, cycling endlessly through the same players.
- The fixed-size cousin of the same idea, the ring buffer, backs audio and network pipelines.
Frequently asked questions
What is the time complexity of a circular linked list?
Insertion at a known position is O(1) - the same pointer writes as any linked list, plus keeping the ring closed. Search is O(n) worst case, and a failed search visits every node exactly once before returning to its starting point. Space is O(n).
How do you traverse a circular linked list without looping forever?
Save a reference to the node you started at, then use a do-while shape: process, hop, and stop when the current node equals the start again. Checking for null never fires - the whole point of the ring is that no pointer is null.
What is a circular linked list used for?
Anything that cycles endlessly through a fixed set: round-robin CPU scheduling, playlists on repeat, turn-taking in games. The ring removes wrap-around checks from every call site, because advancing is always the same single pointer hop - even from the last element back to the first.
How is this different from a list that accidentally has a cycle?
A circular list is a ring on purpose, so you traverse it with a start-node check. An accidental cycle is a bug you detect - that is Floyd's tortoise and hare, covered in its own visualizer, which answers whether an arbitrary list loops at all.