Circular Linked Lists
A circular linked list closes the loop: the last node points back to the first instead of to null. That one change removes the natural stopping point, so traversal needs an explicit guard — and buys O(1) access to both ends from a single pointer.
Closing the Loop
A circular linked list replaces the terminating null with a link from the last node back to the first. Every node then has a genuine successor, and following next repeatedly cycles through the list forever rather than stopping.
Both variants exist. A circular singly linked list gives each node one next pointer, with the tail's pointing at the head. A circular doubly linked list adds prev, so the head's prev points at the tail as well and the loop closes in both directions.
The structural consequence is that there is no distinguished first or last node. Any node can serve as the entry point, and 'head' becomes a matter of which reference you happen to hold rather than a property of the structure. That symmetry is what makes the list suitable for rotation, where a linear list would have to move data.
The cost is that every loop needs a different termination condition. while (current != null) never terminates here. The correct form is a do-while that saves the starting node and stops on returning to it: process the current node, advance, and continue while current != start.
Writing it as a plain while (current != start) fails on the first iteration, since the condition is immediately false — the loop body never runs. This is the standard circular-list bug, and it is why the do-while form is the one to remember.
The empty list needs care too. It cannot be represented by 'head is null and the last node points nowhere', because there is no last node. The usual convention is that an empty circular list has a null head, and a single-node list has a node whose next points at itself — a case worth testing explicitly, since it is easy to write insertion code that leaves the sole node pointing at null instead.
- The tail's
nextpoints at the head — no null anywhere - Any node can act as the entry point; there is no true first
- Loop with do-while, stopping when you return to the start node
- A single-node list has a node pointing at itself
Why Keep the Tail Instead of the Head
A useful implementation choice is to store a reference to the tail rather than the head. It seems arbitrary and is not.
Given the tail, the head is immediately available as tail.next — one dereference, no traversal. So holding the tail gives O(1) access to both ends, where holding the head gives O(1) access to only the head and requires a full O(n) walk to reach the tail.
That makes both insertions cheap. Inserting at the front: create the node, set its next to tail.next (the old head), and point tail.next at it. Inserting at the back: do exactly the same, then additionally reassign tail to the new node. The two operations differ by a single line, which is a neat illustration of how little separates the ends in a circular structure.
This is precisely what a queue needs — enqueue at one end, dequeue at the other, both in O(1) — using one pointer where a linear singly linked list requires two.
Rotation is where the structure genuinely shines. Rotating a linear list by k positions means relinking or moving elements. In a circular list, rotating by one is just tail = tail.next — a single assignment, O(1), with no node touched and no data copied. Rotating by k is k such steps, or O(1) if you can compute the target directly.
Deletion carries the usual singly linked caveat: removing a node requires its predecessor, so it costs O(n) to find unless the list is doubly linked. Deleting the head is O(1) given the tail, since tail.next is the head and tail is its predecessor by definition.
tail.nextis the head, so one pointer reaches both ends- Front and back insertion differ by a single line
- Rotating by one position is
tail = tail.next— O(1) - Deletion still needs the predecessor unless the list is doubly linked
Round-Robin and Ring Buffers
The structure's applications all share one shape: a fixed set of items cycled through repeatedly, with no natural end to the sequence.
Round-robin scheduling is the canonical case. An operating system gives each runnable process a time slice, then moves to the next; after the last, it returns to the first. A circular list expresses this directly — the scheduler holds one pointer and advances it, with no bounds check and no wrap-around branch, because the wrap is the structure itself. The Linux scheduler's run queues use circular doubly linked lists for exactly this reason.
Ring buffers apply the same idea to data rather than tasks: a fixed-size buffer where writing past the end continues at the beginning. Audio and video streaming, keyboard input buffers, and network packet queues all use one, since old data can be overwritten as it becomes irrelevant. In practice a ring buffer is usually built on an array with modulo arithmetic rather than linked nodes — the indices wrap just as the pointers would, with better cache behaviour and no allocation.
That is worth noting honestly: a circular array is the more common implementation of circular behaviour. The linked version wins only when the number of elements changes frequently, since an array's capacity is fixed.
Other uses fit the same pattern. Multiplayer game turn order cycles through players. A carousel or image slideshow returns to the first item after the last. The Josephus problem — people in a circle eliminating every kth person until one remains — is the classic exercise, and simulating it directly with a circular list is the most natural solution, though a mathematical recurrence solves it in O(n) without any structure at all.
- Round-robin scheduling advances one pointer with no wrap check
- Ring buffers overwrite the oldest data — audio, input, packet queues
- A circular array is usually the better implementation of the same idea
- Turn order, carousels, and the Josephus problem share the shape
Terms, operations, and practical uses
Topology
- Ring StructureA linked list that forms a closed loop, where the final node connects back to the first node.
- No Null PointersA properly formed circular list never contains a null reference; traversal can continue infinitely.
- Tail TrackingKeeping a reference to the tail instead of the head, because tail.next provides instant access to the head.
Traversal mechanics
- Starting ReferenceTo traverse a circular list exactly once, you must save the start node and stop when current.next equals the start node.
- Infinite LoopsA common bug if a stopping condition is not correctly implemented when searching for an element.
- Round-RobinContinuously cycling through nodes, giving each a 'turn' before moving to the next.
Applications
- CPU SchedulingGiving multiple processes a tiny slice of CPU time in a repeating circle to simulate multitasking.
- Josephus ProblemA mathematical puzzle where every k-th person in a circle is eliminated until one survives.
- Multiplayer TurnsManaging player turns in a board game, looping back to Player 1 after the last player finishes.
Traversing a Circular Linked List
class Node:
def __init__(self, val):
self.val = val
self.next = None
# Setup the ring A -> B -> C -> D -> A
a = Node("A")
b = Node("B")
c = Node("C")
d = Node("D")
a.next = b
b.next = c
c.next = d
d.next = a # the tail closes the ring
start = a
current = a
while True:
print(current.val)
current = current.next
if current == start:
break#include <iostream>
#include <string>
using namespace std;
struct Node {
string val;
Node* next;
Node(string x) : val(x), next(NULL) {
}
};
int main() {
Node* a = new Node("A");
Node* b = new Node("B");
Node* c = new Node("C");
Node* d = new Node("D");
a->next = b;
b->next = c;
c->next = d;
d->next = a; // the tail closes the ring
Node* start = a;
Node* current = a;
do {
cout << current->val << '\n';
current = current->next;
}
while (current != start);
}class Main {
static class Node {
String val;
Node next;
Node(String x) {
val = x;
}
}
public static void main(String[] args) {
Node a = new Node("A");
Node b = new Node("B");
Node c = new Node("C");
Node d = new Node("D");
a.next = b;
b.next = c;
c.next = d;
d.next = a; // the tail closes the ring
Node start = a;
Node current = a;
do {
System.out.println(current.val);
current = current.next;
}
while (current != start);
}
}Step through it
Running on Ring: A -> B -> C -> D -> A. Print each node once.
Read all 12 Steps
- Build the ring Four nodes are linked A -> B -> C -> D, and D.next points back to A instead of null. There is no end pointer to test against, so a plain `while (current != null)` loop would never stop.
- Remember the start Save `start = A` before moving. This saved reference is the only thing that can end the walk, because no node holds null.
- Visit A Print A. It is the first node of the output and also the node the loop must eventually come back to.
- Advance to B current = current.next moves to B. Compare B against start: they differ, so the ring has more to give.
- Visit B Print B. Two of four nodes are now emitted and current is still not back at start.
- Advance to C current = current.next moves to C. Still not equal to start, so the loop body runs again.
- Visit C Print C. Three nodes emitted. Nothing about C signals that the list is nearly finished — only the start comparison can.
- Advance to D current = current.next moves to D, the tail. In a singly linked list D.next would be null; here it is the head.
- Visit D Print D. Every node has now been emitted exactly once, but the loop has not been told to stop yet.
- Advance wraps to A current = current.next follows D.next, which is A. This is the wrap that makes the list circular — the pointer jumps backwards across the whole structure in one hop.
- current == start, stop The comparison finally succeeds, so the loop exits after exactly four visits. This is why the walk must be a do-while: a plain while would test current == start on the very first iteration and print nothing.
- Why the guard is not optional Drop the `current != start` test and the traversal runs forever, revisiting A, B, C, D endlessly. A circular list trades the free null terminator for a comparison you must supply yourself.
When the Cycle Is a Bug
Circularity is sometimes deliberate and sometimes a defect. A linear list that has accidentally acquired a cycle — through a mistaken pointer assignment during insertion or reversal — will hang any traversal written to stop at null.
Floyd's cycle detection, the tortoise and hare, finds it in O(n) time and O(1) space. Advance a slow pointer one node per step and a fast pointer two. If fast reaches null, the list terminates and there is no cycle. If a cycle exists, fast must enter it and thereafter closes the gap on slow by exactly one node per iteration, so the gap shrinks monotonically and the two are guaranteed to meet.
That closing-by-one argument is what makes the algorithm a proof rather than a heuristic, and it is the part an exam answer needs — 'they meet eventually' without the reason is an incomplete answer.
To find where the cycle begins, reset one pointer to the head after they meet and advance both one step at a time; their next meeting is the entry node. This follows from the distances travelled: the head-to-entry distance equals the meeting-point-to-entry distance measured around the loop.
To measure the cycle's length, keep one pointer fixed at the meeting point and walk the other around until it returns, counting the steps.
The alternative is a hash set of visited nodes, which detects a repeat immediately and is simpler to write, but costs O(n) space. Floyd's is preferred when memory is constrained, and it is the expected answer in interviews for exactly that reason.
For a genuinely circular list, note that these detection algorithms report a cycle by design — so code that must handle both kinds needs to know which it is dealing with rather than inferring it.
- An unintended cycle hangs any traversal expecting a null terminator
- Floyd's algorithm detects it in O(n) time and O(1) space
- The gap closes by one per step, so a meeting is guaranteed
- A hash set is simpler but costs O(n) memory