Traversal of Circular Linked List in DSA C# - 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?

No→Repeat visit and move

Yes↓

Stop traversal

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

Execution Sample

DSA C#

Node current = head;
do {
    Console.WriteLine(current.data);
    current = current.next;
} while (current != head);

Prints all nodes in the circular linked list starting from head until it loops back.

Execution Table

Step	Operation	Current Node Data	Pointer Changes	Visual State
1	Start at head	10	current = head	10 -> 20 -> 30 -> 40 -> (back to 10)
2	Print current.data	10	none	10 -> 20 -> 30 -> 40 -> (back to 10)
3	Move to next node	20	current = current.next	10 -> 20 -> 30 -> 40 -> (back to 10)
4	Print current.data	20	none	10 -> 20 -> 30 -> 40 -> (back to 10)
5	Move to next node	30	current = current.next	10 -> 20 -> 30 -> 40 -> (back to 10)
6	Print current.data	30	none	10 -> 20 -> 30 -> 40 -> (back to 10)
7	Move to next node	40	current = current.next	10 -> 20 -> 30 -> 40 -> (back to 10)
8	Print current.data	40	none	10 -> 20 -> 30 -> 40 -> (back to 10)
9	Move to next node	10	current = current.next	10 -> 20 -> 30 -> 40 -> (back to 10)
10	Check if current == head	10	none	Traversal ends after full circle

💡 Traversal stops when current node returns to head node, completing one full circle.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 9	Final
current.data	10	20	30	40	10	Traversal ends

Key Moments - 3 Insights

Why do we use a do-while loop instead of a while loop?

Because we must visit the head node first before checking if we returned to it. The do-while ensures the loop runs at least once, as shown in steps 1 and 2 of the execution_table.

What happens if the list has only one node?

The traversal prints that single node once and stops immediately after moving back to head, as the condition current == head becomes true after the first move (see exit condition in step 10).

Why do we check current != head after moving to next node?

Because the traversal must stop only after completing the full circle. Checking after moving ensures all nodes including head are visited exactly once, as shown between steps 9 and 10.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of current.data at step 6?

A 30

B 20

C 40

D 10

💡 Hint

Check the 'Current Node Data' column at step 6 in the execution_table.

At which step does the traversal move back to the head node?

A Step 7

B Step 9

C Step 10

D Step 5

💡 Hint

Look at the 'Pointer Changes' and 'Current Node Data' columns showing current moves to 10 again.

If the list had only one node with data 10, how many times would the print operation run?

A 0 times

B 2 times

C 1 time

D Infinite times

💡 Hint

Refer to key_moments about single node list and the do-while loop behavior.

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 do-while loop to ensure head is visited first
- Traverses all nodes exactly once in a circle

Full Transcript

Traversal of a circular linked list starts at the head node. We visit the current node's data, then move to the next node. This repeats until we return to the head node, completing one full circle. A do-while loop is used to ensure the head node is processed before checking the stop condition. The traversal prints each node's data exactly once. If the list has only one node, it prints once and stops immediately after returning to head. The key is to check the stop condition after moving to the next node to avoid missing any nodes or infinite loops.

Practice

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

easy

A. In a circular linked list, traversal stops when the last node's next is null.

B. In a singly linked list, traversal stops when the first node is reached again.

C. In a singly linked list, traversal never ends.

D. In a circular linked list, traversal stops when the starting node is reached again.

Solution

1. Step 1: Understand traversal stopping condition for singly linked list

   Traversal stops when the next pointer is null, indicating the end of the list.

2. Step 2: Understand traversal stopping condition for circular linked list

   Traversal stops when the traversal reaches the starting node again, since the list loops back.

3. Final Answer:

   In a circular linked list, traversal stops when the starting node is reached again. -> Option D

4. Quick Check:

   Circular list stops at start node [OK]

Hint: Remember: circular list loops back to start node [OK]

Common Mistakes:

• Thinking traversal stops at null in circular list
• Confusing stopping conditions of singly and circular lists
• Assuming circular list has a null next pointer

2. Which of the following C# code snippets correctly starts traversal of a circular linked list from the head node?

easy

A. Node current = head; for (int i = 0; i < length; i++) { Console.WriteLine(current.Data); current = current.Next; }

B. Node current = head; while (current != null) { Console.WriteLine(current.Data); current = current.Next; }

C. Node current = head; do { Console.WriteLine(current.Data); current = current.Next; } while (current != head);

D. Node current = head; while (current.Next != null) { Console.WriteLine(current.Data); current = current.Next; }

Solution

1. Step 1: Identify correct loop structure for circular list traversal

   Traversal must use a do-while loop to ensure the head node is processed before checking the condition.

2. Step 2: Check condition to stop traversal

   Traversal stops when current node returns to head, so condition is current != head in while.

3. Final Answer:

   Node current = head; do { Console.WriteLine(current.Data); current = current.Next; } while (current != head); -> Option C

4. Quick Check:

   Use do-while with current != head [OK]

Hint: Use do-while loop to handle circular traversal [OK]

Common Mistakes:

• Using while loop without do causes skipping head node
• Checking for null in circular list causes infinite loop
• Using for loop without length in circular list

3. What will be the output of the following C# code snippet for a circular linked list with nodes containing data 10 -> 20 -> 30 -> (back to 10)?

Node head = new Node(10);
head.Next = new Node(20);
head.Next.Next = new Node(30);
head.Next.Next.Next = head;

Node current = head;
do {
    Console.Write(current.Data + " -> ");
    current = current.Next;
} while (current != head);
Console.WriteLine("null");

medium

A. 10 -> 20 -> 30 -> null

B. 10 -> 20 -> 30 -> 10 -> null

C. 10 -> 20 -> 30 -> 20 -> null

D. 10 -> 20 -> 30 -> 30 -> null

Solution

1. Step 1: Understand the circular linked list structure

   The list nodes are 10 -> 20 -> 30, and 30 points back to 10, making it circular.

2. Step 2: Trace the do-while traversal

   Traversal starts at 10, prints 10, moves to 20, prints 20, moves to 30, prints 30, then moves back to 10 which stops the loop.

3. Final Answer:

   10 -> 20 -> 30 -> null -> Option A

4. Quick Check:

   Traversal prints nodes once until back to head [OK]

Hint: Traversal prints nodes once until back to head [OK]

Common Mistakes:

• Printing extra nodes after loop ends
• Confusing circular list with linear list output
• Not stopping traversal at head node

4. Identify the error in the following C# code snippet that attempts to traverse a circular linked list:

Node current = head;
while (current != null) {
    Console.WriteLine(current.Data);
    current = current.Next;
    if (current == head) break;
}

medium

A. The while condition should check current != head instead of current != null.

B. The while condition should be do-while to include head node.

C. The break condition is missing to stop infinite loop.

D. The code will cause a null reference exception.

Solution

1. Step 1: Analyze the while loop condition

   The condition current != null is incorrect for circular linked list because next is never null.

2. Step 2: Identify correct stopping condition

   The loop should stop when current returns to head, so condition should be current != head.

3. Final Answer:

   The while condition should check current != head instead of current != null. -> Option A

4. Quick Check:

   Use current != head to stop traversal [OK]

Hint: Check for current == head, not null, in circular list [OK]

Common Mistakes:

• Using null check in circular list traversal
• Missing break condition causing infinite loop
• Using while instead of do-while causing skipped node

5. Given a circular linked list where each node contains an integer, write a method to find the sum of all node values. Which approach correctly handles the circular nature without infinite looping?

hard

A. Start at head, use while loop with condition current != null, add node data each iteration.

B. Start at head, use do-while loop adding node data, stop when current returns to head.

C. Start at head, use for loop with fixed length equal to number of nodes, add node data.

D. Start at head, use while loop with condition current.Next != null, add node data.

Solution

1. Step 1: Understand circular list traversal for summation

   Traversal must visit each node exactly once and stop when current returns to head to avoid infinite loop.

2. Step 2: Choose correct loop structure

   Using a do-while loop starting at head and stopping when current == head ensures all nodes are included once.

3. Final Answer:

   Start at head, use do-while loop adding node data, stop when current returns to head. -> Option B

4. Quick Check:

   Use do-while and stop at head for sum [OK]

Hint: Use do-while and stop when current == head [OK]

Common Mistakes:

• Using null checks causing infinite loops
• Missing last node in sum due to wrong loop
• Using for loop without knowing list length