Traversal of Circular Linked List in DSA Python - Execution Trace

Concept Flow - Traversal of Circular Linked List

Start at head node

↓

Visit current node and process data

↓

Move to next node

↓

Check if current node is head again?

Yes→Stop traversal

No↓

Visit current node and process data

Start from the head node, visit each node, move to the next, and stop when you return to the head.

Execution Sample

DSA Python

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

# Assume head is the start of circular linked list
current = head
while True:
    print(current.data)
    current = current.next
    if current == head:
        break

Traverse a circular linked list starting from head and print each node's data once.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start at head	1->2->3->4->(back to 1)	current = head (Node 1)	1 -> 2 -> 3 -> 4 -> (back to 1)
2	Print current.data	1->2->3->4->(back to 1)	current = Node 1	Output: 1
3	Move to next node	1->2->3->4->(back to 1)	current = current.next (Node 2)	Pointer at Node 2
4	Print current.data	1->2->3->4->(back to 1)	current = Node 2	Output: 2
5	Move to next node	1->2->3->4->(back to 1)	current = current.next (Node 3)	Pointer at Node 3
6	Print current.data	1->2->3->4->(back to 1)	current = Node 3	Output: 3
7	Move to next node	1->2->3->4->(back to 1)	current = current.next (Node 4)	Pointer at Node 4
8	Print current.data	1->2->3->4->(back to 1)	current = Node 4	Output: 4
9	Move to next node	1->2->3->4->(back to 1)	current = current.next (Node 1)	Pointer back at Node 1
10	Check if current == head	1->2->3->4->(back to 1)	current == head is True	Stop traversal

💡 Traversal stops when current pointer returns to head node.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 9	Final
current	Node 1 (head)	Node 2	Node 3	Node 4	Node 1 (head)	Traversal stops

Key Moments - 3 Insights

Why do we stop traversal when current equals head again?

Because in a circular linked list, nodes loop back to head. Stopping when current == head prevents infinite looping, as shown in execution_table row 10.

What if the list has only one node?

Traversal prints that single node once and stops immediately after moving back to head, same logic as rows 1-3 but with only one node.

Why do we use a 'while True' loop with a break instead of a normal condition?

Because we must visit the head node first before checking if we returned to it. The break happens after printing and moving, ensuring all nodes are visited once, as in execution_table steps 2-10.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'current' after Step 5?

A Node 2

B Node 3

C Node 4

D Node 1

💡 Hint

Check the 'Pointer Changes' column at Step 5 in execution_table.

At which step does the traversal stop because current equals head again?

A Step 10

B Step 8

C Step 9

D Step 7

💡 Hint

Look for the step where 'current == head is True' in execution_table.

If the circular linked list had only one node, how many times would the loop print the node's data?

A Twice

B Zero times

C Once

D Infinite times

💡 Hint

Refer to key_moments explanation about single-node list traversal.

Concept Snapshot

Traversal of Circular Linked List:
- Start at head node
- Visit and process current node
- Move to next node
- Stop when current returns to head
- Use while True with break to handle circular condition
- Ensures each node visited exactly once

Full Transcript

Traversal of a circular linked list starts at the head node. We visit the current node, process its data, then move to the next node. Because the list loops back to the head, we stop traversal when the current node pointer returns to the head. This prevents infinite loops. The code uses a while True loop with a break condition after moving to the next node and checking if it is the head again. This way, all nodes are visited exactly once. For a single-node list, the traversal prints the node once and stops immediately after returning to head.

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