Traversing Circular Linked Lists
What you'll learn: How to loop through a circular linked list without falling into an infinite loop trap.
The Challenge of Circular Traversal
In a circular linked list, the last node points back to the first instead of pointing to NULL. This creates a continuous loop with no natural "end." If you try to traverse it like a regular linked list (stopping when you hit NULL), you'll loop forever because NULL never appears!
The key insight: You need a different stopping condition—one that detects when you've come full circle.
The Standard Technique
The most common approach uses the head pointer as a sentinel—a marker to tell you when you've completed one full loop.
Here's how it works:
- Start at the head node
- Move to the next node
- Keep going until you return to the head
- Stop when
current == headagain
Think of it like running laps on a circular track. You start at a flagpole, run around, and stop when you see that same flagpole again. The flagpole doesn't move—it's your reference point.
The Loop Pattern
current = head
visit or process current
move to current.next
while current is not head:
visit or process current
move to current.next
Notice we process the head node first, then enter the loop. This ensures we visit every node exactly once—including the starting node—without visiting the head twice.
Avoiding the Infinite Loop
The critical difference from singly linked lists: never check for NULL as your stopping condition. That check would never be true, causing an infinite loop. Always use current != head (or current == head to stop).
Key Takeaway: When traversing circular linked lists, use the head pointer as your stopping condition rather than checking for NULL, ensuring you visit each node exactly once before returning to the start.