Traversal and Printing a Linked List in DSA Rust

Mental Model

We move through each connected box one by one to see what's inside and show it.

Analogy: Imagine a treasure hunt where each clue points to the next clue. You follow each clue in order to find all treasures.

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

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3, print all values

Goal: Show all values in the list in order by visiting each node once

Step 1: start at head node with value 1

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

Why: We begin printing from the first node

Step 2: print value 1 and move to next node

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

Why: After printing current, move forward to continue

Step 3: print value 2 and move to next node

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

Why: Keep printing nodes in order

Step 4: print value 3 and move to next node (null)

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

Why: Reached end of list, stop traversal

Result:

1 -> 2 -> 3 -> null

Annotated Code

DSA Rust

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

// Define a node in the linked list
#[derive(Debug)]
struct Node {
    value: i32,
    next: Option<Rc<RefCell<Node>>>,
}

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

// Function to print all values in the linked list
fn print_list(head: Option<Rc<RefCell<Node>>>) {
    let mut current = head;
    while let Some(node) = current {
        // Print current node's value
        print!("{} -> ", node.borrow().value);
        // Move to next node
        current = node.borrow().next.clone();
    }
    println!("null");
}

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

    // Link nodes: 1 -> 2 -> 3
    node1.borrow_mut().next = Some(node2.clone());
    node2.borrow_mut().next = Some(node3.clone());

    // Print the list
    print_list(Some(node1));
}

while let Some(node) = current {

loop through nodes until we reach the end (null)

print!("{} -> ", node.borrow().value);

print the current node's value

current = node.borrow().next.clone();

advance current to the next node

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; traversal uses O(1) extra space

vs Alternative: Compared to arrays, linked list traversal is similar in time but uses pointers instead of indices

Edge Cases

empty list (head is None)

prints only 'null' with no values

DSA Rust

while let Some(node) = current {

single node list

prints the single value followed by 'null'

DSA Rust

while let Some(node) = current {

When to Use This Pattern

When you need to visit every element in a linked list to read or display values, use traversal by following next pointers until null.

Common Mistakes

Mistake: Forgetting to move to the next node inside the loop, causing an infinite loop
Fix: Always update current to current.next at the end of each loop iteration

Mistake: Trying to access next without checking if current node exists, causing errors
Fix: Use safe checks like 'while let Some(node) = current' to avoid null pointer errors

Summary

It visits each node in the linked list and prints its value in order.

Use it when you want to see or process all elements stored in a linked list.

The key is to start at the head and keep moving to the next node until you reach the end.

Practice

1. What does traversing a linked list mean in simple terms?

easy

A. Reversing the order of nodes

B. Adding a new node at the end

C. Visiting each node one by one from start to end

D. Deleting the first node

Solution

1. Step 1: Understand traversal meaning

   Traversal means going through each element in order, like reading a list from start to finish.

2. Step 2: Match with linked list action

   Visiting each node one by one from start to end matches the idea of traversal.

3. Final Answer:

   Visiting each node one by one from start to end -> Option C

4. Quick Check:

   Traversal = Visit nodes in order [OK]

Hint: Traversal means visiting nodes one by one [OK]

Common Mistakes:

• Confusing traversal with adding or deleting nodes
• Thinking traversal means changing node order

2. Which Rust code snippet correctly traverses and prints a singly linked list named list?

easy

A. let mut current = &list.head;
while let Some(node) = current {
println!("{}", node.value);
current = &node.next;
}

B. for node in list {
println!("{}", node.value);
}

C. while list.head.is_some() {
println!("{}", list.head.value);
list.head = list.head.next;
}

D. let mut current = list.head;
loop {
println!("{}", current.value);
}

Solution

1. Step 1: Check traversal logic

   let mut current = &list.head; while let Some(node) = current { println!("{}", node.value); current = &node.next; } uses a mutable reference to current node and loops while current is Some(node), printing value and moving to next node.

2. Step 2: Verify other options

   for node in list { println!("{}", node.value); } tries for loop on list directly (not valid without iterator). while list.head.is_some() { println!("{}", list.head.value); list.head = list.head.next; } mutates list head which is unsafe. let mut current = list.head; loop { println!("{}", current.value); } loops infinitely without checking for None.

3. Final Answer:

   Option A code snippet -> Option A

4. Quick Check:

   Correct traversal uses while let Some(node) = current [OK]

Hint: Use while let Some(node) = current for safe traversal [OK]

Common Mistakes:

• Trying to loop directly over list without iterator
• Not checking for None to stop loop
• Mutating list head during traversal

3. What will be the output of this Rust code that prints a linked list?

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

fn print_list(head: &Option) {
    let mut current = head;
    while let Some(node) = current {
        print!("{} -> ", node.value);
        current = &node.next;
    }
    println!("null");
}

fn main() {
    let list = Some(Box::new(Node { value: 1, next: Some(Box::new(Node { value: 2, next: Some(Box::new(Node { value: 3, next: None })) })) }));
    print_list(&list);
}

medium

A. 3 -> 2 -> 1 -> null

B. 1 -> 2 -> 3 -> null

C. 1 2 3 null

D. null

Solution

1. Step 1: Understand list structure

   The list nodes are 1 pointing to 2, which points to 3, which points to None.

2. Step 2: Trace print_list function

   It prints each node's value followed by ' -> ', then prints 'null' at the end.

3. Final Answer:

   1 -> 2 -> 3 -> null -> Option B

4. Quick Check:

   Print nodes in order with arrows [OK]

Hint: Follow next pointers to print nodes in order [OK]

Common Mistakes:

• Printing nodes in reverse order
• Missing arrows or null at end
• Printing values without separators

4. Identify the error in this Rust code that tries to print a linked list and fix it:

fn print_list(mut head: Option) {
    while let Some(node) = head {
        println!("{}", node.value);
        head = node.next;
    }
}

medium

A. Code uses wrong print macro println! instead of print!

B. Code does not check for None, causing infinite loop

C. Code does not update head inside the loop

D. Code moves ownership of nodes, so it cannot be reused after printing

Solution

1. Step 1: Analyze ownership in loop

   The code takes ownership of head and nodes inside the loop, consuming the list and preventing reuse.

2. Step 2: Suggest fix using references

   Use references (&Option) and iterate without consuming ownership to allow reuse.

3. Final Answer:

   Code moves ownership of nodes, so it cannot be reused after printing -> Option D

4. Quick Check:

   Ownership moved inside loop causes consumption [OK]

Hint: Use references to avoid moving ownership during traversal [OK]

Common Mistakes:

• Ignoring ownership rules causing compile errors
• Not updating head causing infinite loops
• Confusing print! and println! macros

5. Given a linked list where each node contains an integer, how would you modify the traversal code to print only even values in order?

fn print_even(head: &Option) {
    let mut current = head;
    while let Some(node) = current {
        // Your code here
        current = &node.next;
    }
}

hard

A. Add an if check: if node.value % 2 == 0 { println!("{}", node.value); }

B. Print all values and filter even ones after traversal

C. Change loop to skip nodes with odd values by modifying next pointer

D. Use recursion to print only odd values

Solution

1. Step 1: Add condition inside traversal

   Check if node.value is even using modulo operator and print only if true.

2. Step 2: Keep traversal unchanged

   Continue moving current to next node regardless of value to visit all nodes.

3. Final Answer:

   Add an if check: if node.value % 2 == 0 { println!("{}", node.value); } -> Option A

4. Quick Check:

   Filter values inside traversal with if condition [OK]

Hint: Use if condition inside loop to print only even values [OK]

Common Mistakes:

• Trying to modify next pointer during traversal
• Filtering after traversal instead of during
• Printing odd values instead of even