Traversal and Printing a Linked List in DSA Rust - Execution Trace

Concept Flow - Traversal and Printing a Linked List

Start at head node

↓

Is current node None?

Yes→Stop traversal

No↓

Print current node data

↓

Move to next node

↓

Is current node None?

Start from the head node, check if current node exists, print its data, then move to the next node until the end.

Execution Sample

DSA Rust

struct Node {
    data: i32,
    next: Option<Box<Node>>,
}

fn print_list(head: &Option<Box<Node>>) {
    let mut current = head;
    while let Some(node) = current {
        println!("{}", node.data);
        current = &node.next;
    }
}

This code traverses a linked list from head to end, printing each node's data.

Execution Table

Step	Operation	Current Node Data	Pointer Changes	Visual State
1	Start at head	1	current -> head (Node with data 1)	1 -> 2 -> 3 -> None
2	Print current node data	1	No pointer change	1 -> 2 -> 3 -> None
3	Move to next node	2	current -> node.next (Node with data 2)	1 -> 2 -> 3 -> None
4	Print current node data	2	No pointer change	1 -> 2 -> 3 -> None
5	Move to next node	3	current -> node.next (Node with data 3)	1 -> 2 -> 3 -> None
6	Print current node data	3	No pointer change	1 -> 2 -> 3 -> None
7	Move to next node	None	current -> node.next (None)	1 -> 2 -> 3 -> None
8	Check current node	None	Traversal ends	1 -> 2 -> 3 -> None

💡 Traversal stops when current node is None, meaning end of list reached.

Variable Tracker

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

Key Moments - 3 Insights

Why do we check if current node is None before printing?

Because if current is None, it means we've reached the end of the list and there is no data to print. This is shown in execution_table step 8 where traversal stops.

Why do we move current to node.next after printing?

To advance to the next node in the list so we can print its data next. This is shown in steps 3, 5, and 7 where current pointer changes to the next node.

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

The traversal stops immediately because current is None at start, so no printing happens. This is implied by the exit condition in step 8.

Visual Quiz - 3 Questions

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

A Node with data 2

B Node with data 3

C None

D Node with data 1

💡 Hint

Check the 'Pointer Changes' column at step 5 in execution_table.

At which step does the traversal stop because current is None?

A Step 6

B Step 7

C Step 8

D Step 5

💡 Hint

Look at the 'Operation' and 'Current Node Data' columns in execution_table for when current becomes None.

If the list had only one node, how many times would the print operation occur?

A 1 time

B 0 times

C 2 times

D 3 times

💡 Hint

Refer to variable_tracker and execution_table to see how many nodes are printed.

Concept Snapshot

Traversal and Printing a Linked List:
- Start at head node
- While current node is not None:
  - Print current node data
  - Move to next node
- Stop when current is None (end of list)

Full Transcript

Traversal and printing a linked list means starting from the head node and moving through each node one by one. At each node, we print its data. We continue moving to the next node until we reach the end, which is when the current node is None. This process ensures all nodes are visited and their data displayed in order.

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