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)Saved in this browser - no sign-up, nothing sent anywhere.
How 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 LinkedList:
def __init__(self):
self.head = None
def insert_head(self, v):
n = Node(v)
n.next = self.head # O(1) - nothing shifts
self.head = n
def insert_tail(self, v):
n = Node(v)
if not self.head:
self.head = n
return
cur = self.head
while cur.next: # O(n) without a tail pointer
cur = cur.next
cur.next = n
def search(self, v):
cur, i = self.head, 0
while cur:
if cur.value == v:
return i
cur, i = cur.next, i + 1
return -1JavaScript
class Node {
constructor(value) { this.value = value; this.next = null; }
}
class LinkedList {
head = null;
insertHead(v) {
const n = new Node(v);
n.next = this.head;
this.head = n; // O(1)
}
search(v) {
let cur = this.head, i = 0;
while (cur) { // O(n) - no random access
if (cur.value === v) return i;
cur = cur.next; i++;
}
return -1;
}
}Worth noticing
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.
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.