Traversal of Circular Linked List in DSA Rust - Build from Scratch

Traversal of Circular Linked List

📖 Scenario: Imagine you have a group of friends sitting in a circle, passing a message around. This circle never ends because the last friend passes the message back to the first friend. This is like a circular linked list in programming.

🎯 Goal: You will create a circular linked list with three nodes, then write code to visit each node exactly once and print its value.

📋 What You'll Learn

Create a struct called Node with a value and a next pointer

Create three nodes with values 10, 20, and 30

Link the nodes to form a circular linked list

Write a loop to traverse the circular linked list starting from the head node

Print each node's value during traversal exactly once

💡 Why This Matters

🌍 Real World

Circular linked lists are used in real-world applications like music playlists, where the list loops back to the start, or in multiplayer games to cycle turns among players.

💼 Career

Understanding circular linked lists helps in jobs involving system programming, game development, and designing efficient data structures for continuous looping processes.

1

Create the Node struct and three nodes

Define a struct called Node with a field value of type i32 and a field next of type Option<&'static Node>. Then create three nodes named node1, node2, and node3 with values 10, 20, and 30 respectively.

DSA Rust

// Define struct Node and create node1, node2, node3 with values 10, 20, 30
// Your code here

Hint

Use struct to define Node. Use Option<&'static Node> for the next pointer to allow linking nodes.

2

Link the nodes to form a circular linked list

Inside an unsafe block, set node1.next to Some(&node2), node2.next to Some(&node3), and node3.next to Some(&node1) to complete the circle.

DSA Rust

struct Node {
    value: i32,
    next: Option,
}

static mut node1: Node = Node { value: 10, next: None };
static mut node2: Node = Node { value: 20, next: None };
static mut node3: Node = Node { value: 30, next: None };

// Link nodes to form a circular linked list inside unsafe block
// Your code here

Hint

Use an unsafe block to modify static mutable variables. Assign Some(&nodeX) to the next fields to link nodes.

3

Traverse the circular linked list

Inside the unsafe block in main, create a variable current set to &node1. Use a loop to print current.value and then move current to current.next.unwrap(). Stop the loop after printing the value 30 once to avoid infinite looping.

DSA Rust

struct Node {
    value: i32,
    next: Option,
}

static mut node1: Node = Node { value: 10, next: None };
static mut node2: Node = Node { value: 20, next: None };
static mut node3: Node = Node { value: 30, next: None };

fn main() {
    unsafe {
        node1.next = Some(&node2);
        node2.next = Some(&node3);
        node3.next = Some(&node1);

        // Traverse the circular linked list and print values
        // Your code here
    }
}

Hint

Use a loop to visit each node. Print the value, then move to the next node using unwrap(). Stop when you reach the node with value 30.

4

Print the traversal output

Run the program to print the values of the circular linked list nodes in order: 10, 20, 30, each on its own line.

DSA Rust

struct Node {
    value: i32,
    next: Option,
}

static mut node1: Node = Node { value: 10, next: None };
static mut node2: Node = Node { value: 20, next: None };
static mut node3: Node = Node { value: 30, next: None };

fn main() {
    unsafe {
        node1.next = Some(&node2);
        node2.next = Some(&node3);
        node3.next = Some(&node1);

        let mut current = &node1;
        loop {
            println!("{}", current.value);
            if current.value == 30 {
                break;
            }
            current = current.next.unwrap();
        }
    }
}

// Run the program to see output

Hint

The program should print the values 10, 20, and 30 each on a new line.

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