Traversal of Circular Linked List in DSA Rust

Mental Model

A circular linked list connects the last node back to the first, so traversal loops endlessly unless stopped carefully.

Analogy: Imagine a merry-go-round where horses go in a circle; you can keep riding around, but you decide when to stop after one full round.

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

Dry Run Walkthrough

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

Goal: Visit each node exactly once and stop to avoid infinite loop

Step 1: start at head node with value 1

head -> [curr->1] -> 2 -> 3 -> head

Why: We begin traversal from the first node

Step 2: print current node value 1, move curr to next node

head -> 1 -> [curr->2] -> 3 -> head

Why: Visit node 1 and advance to node 2

Step 3: print current node value 2, move curr to next node

head -> 1 -> 2 -> [curr->3] -> head

Why: Visit node 2 and advance to node 3

Step 4: print current node value 3, move curr to next node

head -> 1 -> 2 -> 3 -> [curr->head]

Why: Visit node 3 and advance to head to detect full circle

Step 5: curr equals head, stop traversal

head -> 1 -> 2 -> 3 -> head (stop)

Why: We completed one full cycle, so stop to avoid infinite loop

Result:

1 -> 2 -> 3 -> null

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct Node {
    val: i32,
    next: Option<Rc<RefCell<Node>>>,
}

impl Node {
    fn new(val: i32) -> Rc<RefCell<Node>> {
        Rc::new(RefCell::new(Node { val, next: None }))
    }
}

fn traverse_circular_list(head: Option<Rc<RefCell<Node>>>) {
    if head.is_none() {
        return; // empty list
    }
    let head = head.unwrap();
    let mut curr = Rc::clone(&head);
    loop {
        print!("{} -> ", curr.borrow().val); // print current node value
        curr = match &curr.borrow().next {
            Some(next_node) => Rc::clone(next_node),
            None => break, // should not happen in circular list
        };
        if Rc::ptr_eq(&curr, &head) {
            break; // completed full circle
        }
    }
    print!("null\n");
}

fn main() {
    // Create nodes
    let node1 = Node::new(1);
    let node2 = Node::new(2);
    let node3 = Node::new(3);

    // Link nodes in circular fashion
    node1.borrow_mut().next = Some(Rc::clone(&node2));
    node2.borrow_mut().next = Some(Rc::clone(&node3));
    node3.borrow_mut().next = Some(Rc::clone(&node1));

    // Traverse and print
    traverse_circular_list(Some(node1));
}

if head.is_none() { return; }

handle empty list by stopping traversal

let mut curr = Rc::clone(&head);

start traversal from head node

print!("{} -> ", curr.borrow().val);

print current node value

curr = match &curr.borrow().next { Some(next_node) => Rc::clone(next_node), None => break };

advance curr to next node, break if next is None (should not happen)

if Rc::ptr_eq(&curr, &head) { break; }

stop traversal after completing full circle

Output

1 -> 2 -> 3 -> null

Complexity Analysis

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

Space: O(n) due to storing n nodes in memory for the list

vs Alternative: Compared to linear linked list traversal, circular traversal requires a stop condition to avoid infinite loops but has the same O(n) time complexity

Edge Cases

empty list

function returns immediately without printing

DSA Rust

if head.is_none() { return; }

single node circular list

prints the single node once and stops

DSA Rust

if Rc::ptr_eq(&curr, &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 with a stop condition to avoid infinite loops.

Common Mistakes

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

Mistake: Not handling empty list input, causing runtime errors
Fix: Check if head is None before traversal and return early

Summary

It visits each node in a circular linked list exactly once without looping forever.

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

The key is to stop traversal when you return to the starting node to avoid infinite loops.

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