Circular Linked List
Overview
A Circular Linked List is a variation of a linked list where the last node points back to the first node (or head) instead of pointing to `null`. This forms a continuous loop. It's especially useful for applications that require round-robin scheduling (like OS task scheduling) or representing circular queues where you need to continuously cycle through the elements.
Syntax
By tracking the `tail` node instead of the `head`, you instantly have access to both the end of the list (`tail`) and the beginning of the list (`tail.next`), allowing O(1) insertions at both ends.
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
public class CircularLinkedList {
Node tail; // Instead of head, tracking tail is more efficient for O(1) insertions at both front and rear.
public void insert(int data) {
Node newNode = new Node(data);
if (tail == null) {
tail = newNode;
tail.next = tail; // Points to itself
} else {
newNode.next = tail.next;
tail.next = newNode;
tail = newNode;
}
}
}Common Pitfalls
- Infinite loops! Forgetting the stop condition `while (current != head)` will cause the program to traverse the circle forever.
- Deleting the very last remaining node requires explicitly setting the tail pointer back to `null`.
Interview Tips
- In interviews, emphasize tracking the `tail` rather than the `head`. `tail.next` is automatically the head.
Real-World Example
Operating Systems use Circular Linked Lists to manage a pool of applications that share CPU time (Round Robin scheduling). When an app's time slice is over, the pointer moves to the next app in the circle.
public void roundRobinTraversal() {
if (tail == null) return;
Node current = tail.next; // Start at the head
do {
System.out.println("Processing: " + current.data);
current = current.next;
} while (current != tail.next); // Stop when we complete the circle
}