Traversal of Circular Linked List in DSA Rust - 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 at the head node, visit each node, move to the next, and stop when you return to the head.

Execution Sample

DSA Rust

fn traverse(head: &Option<Box<Node>>) {
    if head.is_none() { return; }
    let mut current = head.as_ref();
    loop {
        println!("{}", current.unwrap().data);
        current = current.unwrap().next.as_ref();
        if std::ptr::eq(current.unwrap(), head.as_ref().unwrap()) { break; }
    }
}

Traverse a circular linked list starting from head, printing each node's data once.

Execution Table

Step	Operation	Current Node Data	Pointer Changes	Visual State
1	Start at head	1	current = head (Node 1)	1 -> 2 -> 3 -> 1 (circular)
2	Print data	1	No pointer change	1 -> 2 -> 3 -> 1 (circular)
3	Move to next	2	current = Node 2	1 -> 2 -> 3 -> 1 (circular)
4	Print data	2	No pointer change	1 -> 2 -> 3 -> 1 (circular)
5	Move to next	3	current = Node 3	1 -> 2 -> 3 -> 1 (circular)
6	Print data	3	No pointer change	1 -> 2 -> 3 -> 1 (circular)
7	Move to next	1	current = Node 1 (head)	1 -> 2 -> 3 -> 1 (circular)
8	Check if current == head	1	Condition true, break loop	Traversal ends

💡 Traversal stops when current node returns to head node.

Variable Tracker

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

Key Moments - 3 Insights

Why do we stop traversal when current node equals head again?

Because the list is circular, reaching head again means we completed one full cycle. See execution_table step 8 where the condition current == head is true, so traversal stops.

What happens if the list is empty (head is None)?

The function returns immediately without any traversal, as shown in the code's first line. No steps occur in execution_table in this case.

Why do we use current = current.next instead of current.next.next?

We move one node at a time to visit each node exactly once. Skipping nodes would miss data. Execution_table steps 3, 5, and 7 show moving to the immediate next node.

Visual Quiz - 3 Questions

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

A Node 1 (head)

B Node 2

C Node 3

D Traversal ends

💡 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 8

B Step 6

C Step 7

D Step 5

💡 Hint

Look at the 'Check if current == head' operation in execution_table.

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

A Twice

B Once

C Zero times

D Infinite times

💡 Hint

Think about the condition that stops traversal when current returns to head.

Concept Snapshot

Traversal of Circular Linked List:
- Start at head node
- Visit and process current node
- Move to next node
- Stop when current node is head again
- Ensures each node is visited exactly once
- Handles empty list by no traversal

Full Transcript

Traversal of a circular linked list starts at the head node. We visit each node by printing its data, then move to the next node. Because the list is circular, we stop traversal when we return to the head node to avoid infinite loops. If the list is empty, no traversal happens. This method ensures every node is visited exactly once in a cycle.

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, nodes have two pointers instead of one.

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

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

D. In a circular linked list, nodes cannot be traversed.

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 null pointer, not looping back.

3. Final Answer:

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

4. Quick Check:

   Last node points to first node = A [OK]

Hint: Remember: circular means last node links back to start [OK]

Common Mistakes:

• Thinking circular lists have two pointers per node
• Confusing circular linked list with doubly linked list
• Assuming nodes are stored in arrays

2. Which Rust code snippet correctly starts traversal of a circular linked list from the head node?

easy

A. let mut current = head;
loop {
println!("{}", current.data);
current = current.next.unwrap();
if current == head { break; }
}

B. let mut current = head;
while current != None {
println!("{}", current.data);
current = current.next;
}

C. for node in head {
println!("{}", node.data);
}

D. let mut current = head;
loop {
println!("{}", current.data);
current = current.next.unwrap();
}

Solution

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

   let mut current = head; loop { println!("{}", current.data); current = current.next.unwrap(); if current == head { break; } } uses a loop that breaks when current returns to head, correctly handling circular traversal.

2. Step 2: Check other options for errors

   let mut current = head; while current != None { println!("{}", current.data); current = current.next; } uses while with None check, which is incorrect for circular lists. for node in head { println!("{}", node.data); } uses for loop on head, invalid syntax. let mut current = head; loop { println!("{}", current.data); current = current.next.unwrap(); } loops infinitely without break.

3. Final Answer:

   let mut current = head; loop { println!("{}", current.data); current = current.next.unwrap(); if current == head { break; } } -> Option A

4. Quick Check:

   Loop until current == head = A [OK]

Hint: Use loop with break when current equals head [OK]

Common Mistakes:

• Using while with None check in circular list
• Forgetting to break loop on returning to head
• Using invalid for loop syntax on linked list

3. What will be the output of the following Rust code that traverses a circular linked list with nodes containing values 10, 20, 30?

let mut current = head;
loop {
    print!("{} ", current.data);
    current = current.next.unwrap();
    if current == head { break; }
}

medium

A. Runtime error due to infinite loop

B. 10 20 30 10

C. 20 30 10

D. 10 20 30

Solution

1. Step 1: Understand traversal logic

   The loop prints current.data, moves to next, and breaks when current equals head again.

2. Step 2: Trace the output

   Starting at 10, prints 10, moves to 20, prints 20, moves to 30, prints 30, moves to 10 (head), breaks loop.

3. Final Answer:

   10 20 30 -> Option D

4. Quick Check:

   Print nodes once until back to head = D [OK]

Hint: Stop printing when current node equals head again [OK]

Common Mistakes:

• Printing extra head node again after loop
• Assuming infinite loop without break
• Starting traversal from wrong node

4. Identify the bug in this Rust code snippet for traversing a circular linked list:

let mut current = head;
while current != head {
    println!("{}", current.data);
    current = current.next.unwrap();
}

medium

A. The code causes infinite loop because no break condition.

B. The unwrap() causes panic if next is None.

C. The loop never executes because current == head initially.

D. The println! macro is used incorrectly.

Solution

1. Step 1: Analyze loop condition

   The while loop condition is current != head, but current starts as head, so condition is false immediately.

2. Step 2: Understand effect on execution

   Loop body never runs, so no traversal happens.

3. Final Answer:

   The loop never executes because current == head initially. -> Option C

4. Quick Check:

   Loop condition false at start = B [OK]

Hint: Check initial loop condition matches traversal logic [OK]

Common Mistakes:

• Using while current != head instead of loop with break
• Ignoring that current starts at head
• Assuming unwrap() always safe without checking

5. You want to sum all values in a circular linked list of integers using Rust. Which approach correctly avoids infinite loops and sums all nodes exactly once?

hard

A. Use a loop starting at head, add current.data, move to next, break when current == head again.

B. Use a while loop checking current != None, add current.data, move to next.

C. Use recursion without base case to traverse nodes and sum values.

D. Use a for loop over head assuming it implements Iterator.

Solution

1. Step 1: Understand circular list traversal for summation

   We must visit each node once and stop when we return to head to avoid infinite loops.

2. Step 2: Evaluate options

   Use a loop starting at head, add current.data, move to next, break when current == head again. uses loop with break on current == head, correctly summing once. Use a while loop checking current != None, add current.data, move to next. uses None check which is invalid for circular lists. Use recursion without base case to traverse nodes and sum values. causes infinite recursion. Use a for loop over head assuming it implements Iterator. assumes Iterator trait which is not standard for linked lists.

3. Final Answer:

   Use a loop starting at head, add current.data, move to next, break when current == head again. -> Option A

4. Quick Check:

   Loop with break on head = C [OK]

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

Common Mistakes:

• Using None checks in circular lists
• Recursing without base case causing stack overflow
• Assuming linked list implements Iterator trait