Traversal and Printing a Linked List in DSA Rust - Build from Scratch

Traversal and Printing a Linked List

📖 Scenario: You are working with a simple linked list that stores numbers. You want to see all the numbers in the list by going through each node one by one.

🎯 Goal: Build a Rust program that creates a linked list with three nodes, then traverses the list to print all the values in order.

📋 What You'll Learn

Create a linked list with three nodes containing the values 10, 20, and 30

Use a variable called current to traverse the list

Print the values of the linked list nodes in order separated by -> and ending with null

💡 Why This Matters

🌍 Real World

Linked lists are used in many programs to store data where the size can change, like playlists or undo history.

💼 Career

Understanding linked lists helps in jobs involving system programming, game development, and any role requiring efficient data management.

1

Create the linked list nodes

Create a struct called Node with a field value of type i32 and a field next of type Option>. Then create three nodes with values 10, 20, and 30 linked together, and assign the head node to a variable called head.

DSA Rust

// Define the Node struct and create the linked list nodes
// Your code here

Hint

Use Option> for the next field to allow linking nodes.

2

Set up traversal variable

Inside the main function, create a mutable variable called current and set it to a reference to head. This variable will help you move through the linked list.

DSA Rust

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

fn main() {
    let node3 = Node { value: 30, next: None };
    let node2 = Node { value: 20, next: Some(Box::new(node3)) };
    let head = Node { value: 10, next: Some(Box::new(node2)) };

    // Create a mutable variable current as a reference to head
    // Your code here
}

Hint

Use let mut current = &head; to start traversal from the head node.

3

Traverse the linked list

Use a while loop to traverse the linked list using the current variable. Inside the loop, print the value of the current node followed by -> . Then update current to point to the next node by accessing current.next. Stop when current is None.

DSA Rust

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

fn main() {
    let node3 = Node { value: 30, next: None };
    let node2 = Node { value: 20, next: Some(Box::new(node3)) };
    let head = Node { value: 10, next: Some(Box::new(node2)) };

    let mut current = &head;

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

Hint

Use while let Some(next_node) = ¤t.next to loop until the end of the list.

4

Print the linked list

Add a print statement to display the linked list values in order separated by -> and ending with null. The output should look like: 10 -> 20 -> 30 -> null.

DSA Rust

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

fn main() {
    let node3 = Node { value: 30, next: None };
    let node2 = Node { value: 20, next: Some(Box::new(node3)) };
    let head = Node { value: 10, next: Some(Box::new(node2)) };

    let mut current = &head;

    // Print the linked list values
    // Your code here
}

Hint

Make sure the output ends with null to show the list 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