Circular Linked List
Overview
A Circular Linked List is a variation of a linked list in which the last node points back to the first node, forming a complete circle. There is no null at the end of the list.
Circular lists can be singly linked or doubly linked. The primary advantage of a circular list is that any node can be a starting point, and you can traverse the entire list starting from absolutely anywhere. This is particularly useful in applications that require continuous looping, like an OS round-robin task scheduler or a multiplayer board game turn system.
However, this infinite loop property makes traversal dangerous. If you write a standard while(current != null) loop, your program will get stuck in an infinite loop and crash. You must always maintain a reference to the starting node and stop traversing when current.next == startNode.
Syntax
public class CircularLinkedList {
static class Node {
int data;
Node next;
Node(int data) { this.data = data; }
}
Node tail = null; // In circular lists, tracking the tail is more useful than head
public void add(int data) {
Node newNode = new Node(data);
if (tail == null) {
tail = newNode;
tail.next = tail; // Point to itself!
} else {
newNode.next = tail.next; // New node points to the head
tail.next = newNode; // Old tail points to new node
tail = newNode; // New node becomes the tail
}
}
public void printList() {
if (tail == null) return;
Node head = tail.next;
Node current = head;
do {
System.out.print(current.data + " -> ");
current = current.next;
} while (current != head); // Stop when we complete the circle!
System.out.println("(back to start)");
}
}Common Pitfalls
- Infinite loops during traversal. The standard
while (current != null)pattern does not work because there is no null in a circular list. You must use ado-whileloop and check ifcurrent != head. - Losing track of the list bounds. Since it's a circle, the concepts of 'head' and 'tail' are purely logical, not structural. If your pointer management is sloppy during insertions or deletions, you can easily orphan nodes or break the circle.
- Complexity in deleting nodes. Deleting the head node requires traversing the entire list to update the tail's
nextpointer to the new head (unless it's doubly linked), making it O(N) time.
Interview Questions
tail instead of the head?If you only have a head pointer, appending to the end takes O(N) time because you must traverse the whole circle to find the tail to update its next pointer. If you keep a tail pointer, you have instant O(1) access to BOTH the tail and the head (since tail.next == head). This makes O(1) insertions at both ends possible.
Use the Fast and Slow Pointer technique. Move fast by two steps and slow by one step. When fast.next == head or fast.next.next == head, the slow pointer is at the midpoint. You then break the circle and re-wire the pointers to form two separate circular lists.
Real-World Example
A multiplayer game turn system. Players sit in a circle, and when one player's turn ends, it goes to the next. If a player leaves the game, their node is deleted, and the circle closes. There is no 'end' to the list until the game finishes.
class GameState {
PlayerNode currentPlayer;
public void nextTurn() {
// Instantly move to the next player, looping back seamlessly
currentPlayer = currentPlayer.next;
System.out.println("It's now " + currentPlayer.name + "'s turn!");
}
public void playerLeft(PlayerNode player) {
// Find player and remove them, bridging the circle
// ... deletion logic ...
}
}Check Your Knowledge
Test your understanding of Circular Linked List with these quick questions.