Traversal of Circular Linked List in DSA Python

Mental Model

A circular linked list loops back to the start, so traversal must stop when we return to the first node to avoid infinite loops.

Analogy: Imagine walking around a circular track; you keep moving forward until you reach the starting point again, then you stop.

head -> 1 -> 2 -> 3 ->
          ↑         ↓
          ← ← ← ← ← ←

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> back to 1 (circular), traverse and print all nodes

Goal: Visit each node exactly once and stop after returning to the start

Step 1: Start at head node with value 1

[curr->1] -> 2 -> 3 -> back to 1

Why: We begin traversal from the first node

Step 2: Move curr to next node with value 2

1 -> [curr->2] -> 3 -> back to 1

Why: Visit the next node in the list

Step 3: Move curr to next node with value 3

1 -> 2 -> [curr->3] -> back to 1

Why: Continue traversal to next node

Step 4: Move curr to next node which is head (value 1), stop traversal

[curr->1] -> 2 -> 3 -> back to 1

Why: We reached the start again, so traversal ends to avoid infinite loop

Result:

1 -> 2 -> 3 -> back to 1 (traversal stops here)

Annotated Code

DSA Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class CircularLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head
            return
        curr = self.head
        while curr.next != self.head:
            curr = curr.next
        curr.next = new_node
        new_node.next = self.head

    def traverse(self):
        if not self.head:
            print("List is empty")
            return
        curr = self.head
        while True:
            print(curr.data, end=" -> ")
            curr = curr.next
            if curr == self.head:
                break
        print("back to head")

# Driver code
cll = CircularLinkedList()
cll.append(1)
cll.append(2)
cll.append(3)
cll.traverse()

while curr.next != self.head:

advance curr to last node before head to append new node

while True:

start infinite loop to traverse circular list

print(curr.data, end=" -> ")

print current node's data

curr = curr.next

advance curr to next node

if curr == self.head:

stop traversal when we return to head node

Output

1 -> 2 -> 3 -> back to head

Complexity Analysis

Time: O(n) because we visit each of the n nodes exactly once during traversal

Space: O(1) because we use only a few pointers regardless of list size

vs Alternative: Compared to linear linked list traversal, circular traversal requires a check to stop at head to avoid infinite loops

Edge Cases

empty list

prints 'List is empty' and stops

DSA Python

if not self.head:
    print("List is empty")
    return

single node list

prints the single node once and stops after returning to head

DSA Python

if curr == self.head:
    break

When to Use This Pattern

When you see a linked list where the last node points back to the first, use circular linked list traversal by stopping when you reach the head again to avoid infinite loops.

Common Mistakes

Mistake: Not checking if current node is head again, causing infinite loop
Fix: Add a condition to break traversal when current node equals head

Mistake: Not handling empty list before traversal
Fix: Check if head is None and handle empty case before traversal

Summary

It visits each node in a circular linked list exactly once by stopping when it returns to the start.

Use it when you need to process or print all elements in a circular linked list safely.

The key insight is to stop traversal when you reach the head again to avoid looping forever.

Practice

1. What is the main difference between a circular linked list and a regular singly linked list?

easy

A. In a circular linked list, the last node points back to the first node.

B. In a circular linked list, nodes have two pointers instead of one.

C. In a circular linked list, nodes are stored in an array.

D. In a circular linked list, the first node points to null.

Solution

1. Step 1: Understand the structure of a circular linked list

   A circular linked list connects the last node back to the first node, forming a circle.

2. Step 2: Compare with a regular singly linked list

   A regular singly linked list ends with a node pointing to null, not back to the first node.

3. Final Answer:

   In a circular linked list, the last node points back to the first node. -> Option A

4. Quick Check:

   Circular linked list last node points to first node [OK]

Hint: Remember: circular means last node loops to first [OK]

Common Mistakes:

• Thinking circular lists have two pointers per node
• Confusing circular linked list with doubly linked list
• Assuming last node points to null

2. Which of the following is the correct way to start traversing a circular linked list in Python?

easy

A. current = head
while current is not None:
print(current.data)
current = current.next

B. current = head
while True:
print(current.data)
current = current.next
if current == head:
break

C. current = head
for i in range(len(list)):
print(current.data)
current = current.next

D. current = head
while current.next is not None:
print(current.data)
current = current.next

Solution

1. Step 1: Understand traversal stopping condition for circular list

   Traversal must stop when current node comes back to head to avoid infinite loop.

2. Step 2: Check code options for correct loop and break condition

   current = head while True: print(current.data) current = current.next if current == head: break uses while True with break when current equals head, correctly handling circular traversal.

3. Final Answer:

   Use while True loop and break when current equals head. -> Option B

4. Quick Check:

   Stop traversal when current == head [OK]

Hint: Use break when current node equals head to stop [OK]

Common Mistakes:

• Using None as stopping condition in circular list
• Forgetting to break loop causing infinite traversal
• Using length which is not defined for linked list

3. What will be the output of the following code snippet?

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = Node(10)
second = Node(20)
third = Node(30)

head.next = second
second.next = third
third.next = head  # circular link

current = head
count = 0
while True:
    print(current.data, end=' ')
    current = current.next
    count += 1
    if count == 4:
        break

medium

A. 10 20 30 30

B. 10 20 30

C. 10 20 30 10

D. 10 20 20 10

Solution

1. Step 1: Trace the nodes and their links

   Nodes are 10 -> 20 -> 30 -> back to 10 forming a circle.

2. Step 2: Follow the loop for 4 iterations

   Prints: 10 (count=1), 20 (2), 30 (3), 10 (4) then breaks.

3. Final Answer:

   10 20 30 10 -> Option C

4. Quick Check:

   4 prints following circular links [OK]

Hint: Count iterations to avoid infinite loop in circular list [OK]

Common Mistakes:

• Stopping after 3 prints assuming no repetition
• Printing wrong node data due to pointer confusion
• Ignoring circular link causing infinite loop

4. The following code is intended to traverse a circular linked list and print all node data once. What is the error?

current = head
while current != head:
    print(current.data)
    current = current.next

medium

A. The code will raise an AttributeError.

B. The loop will run infinitely because no break condition.

C. The code will print only the head node data once.

D. The loop never starts because current == head initially.

Solution

1. Step 1: Analyze the loop condition at start

   current is initialized to head, so current != head is False initially.

2. Step 2: Understand loop execution

   Since condition is False, loop body never executes, so no data is printed.

3. Final Answer:

   The loop never starts because current == head initially. -> Option D

4. Quick Check:

   Loop condition false at start stops loop [OK]

Hint: Check initial loop condition carefully in circular traversal [OK]

Common Mistakes:

• Assuming loop runs at least once
• Using != head as loop condition without special handling
• Not using do-while style logic for circular lists

5. You have a circular linked list with nodes containing values [5, 15, 25, 35]. Write a Python function to traverse and collect all node values in a list without infinite looping. What is the correct output of your function?

hard

A. [5, 15, 25, 35]

B. [5, 15, 25, 35, 5]

C. [15, 25, 35, 5]

D. [5, 15, 25]

Solution

1. Step 1: Traverse circular list starting at head

   Start at head node with value 5 and move to next nodes collecting values.

2. Step 2: Stop traversal when current node returns to head

   Collect values 5, 15, 25, 35 and stop before repeating 5 again.

3. Final Answer:

   [5, 15, 25, 35] -> Option A

4. Quick Check:

   Collect all unique nodes once [OK]

Hint: Stop when current node equals head to avoid repeats [OK]

Common Mistakes:

• Including head node twice causing extra element
• Stopping too early missing last node
• Infinite loop by not checking for head again