Traversal and Printing a Linked List in DSA Rust - Deep Dive

Overview - Traversal and Printing a Linked List

What is it?

Traversal and printing a linked list means going through each element in the list one by one and showing its value. A linked list is a chain of nodes where each node points to the next. Traversal helps us see or use all the data stored in the list. Printing is simply showing these values in order.

Why it matters

Without traversal, we cannot access or use the data inside a linked list because the nodes are not stored next to each other like in an array. Traversal lets us visit every node to read or change its value. If we could not traverse, linked lists would be useless for storing sequences of data.

Where it fits

Before learning traversal, you should understand what a linked list is and how nodes link together. After mastering traversal and printing, you can learn how to insert or delete nodes, reverse the list, or search for values.

Mental Model

Core Idea

Traversal is like following a chain link by link from the start to the end to see every item in order.

Think of it like...

Imagine a treasure hunt where each clue leads you to the next one. You start at the first clue and follow each hint until you reach the last. Traversal is following these clues one by one.

Head -> [Node1 | Next] -> [Node2 | Next] -> [Node3 | Next] -> None

Traversal starts at Head and moves through each Next pointer until None.

Build-Up - 6 Steps

1

Foundation

Understanding Linked List Structure

Concept: Learn what a linked list node contains and how nodes connect.

A linked list node holds two things: data (like a number or word) and a pointer to the next node. The last node points to None, meaning the list ends there. This structure allows nodes to be scattered in memory but still connected.

Result

You can picture a chain of nodes where each node knows where the next one is.

Knowing the node structure is key because traversal depends on following these next pointers.

2

Foundation

Starting Point: The Head Node

Concept: Traversal always begins at the head, the first node in the list.

The head is a special pointer that tells us where the list starts. Without the head, we cannot find any nodes. Traversal uses the head to begin visiting nodes one by one.

Result

You understand that the head is your entry point to the entire list.

Recognizing the head as the starting point prevents confusion about where to begin traversal.

3

Intermediate

Simple Traversal Loop in Rust

🤔Before reading on: do you think traversal uses recursion or a loop? Commit to your answer.

Concept: Use a loop to move through nodes until reaching None.

In Rust, you can use a while let loop to check if the current node exists. Start with head, print its data, then move to the next node. Repeat until no more nodes remain. Example: let mut current = &head; while let Some(node) = current { println!("{}", node.data); current = &node.next; }

Result

All node data prints in order from head to end.

Understanding the loop condition with Option types in Rust is crucial for safe traversal without errors.

4

Intermediate

Handling Empty Lists Gracefully

🤔Before reading on: do you think an empty list causes errors during traversal? Commit to yes or no.

Concept: Check if the head is None before starting traversal.

An empty list has head set to None. Before looping, check if head is None. If yes, print a message or do nothing. This avoids trying to access nodes that don't exist. Example: if head.is_none() { println!("List is empty"); } else { // traverse }

Result

Program safely handles empty lists without crashing.

Knowing to check for None first prevents runtime errors and improves program robustness.

5

Advanced

Implementing Display Trait for Printing

🤔Before reading on: do you think printing each node manually is the best way? Commit to yes or no.

Concept: Use Rust's Display trait to customize how the whole list prints.

Instead of printing nodes one by one outside, implement the Display trait for the linked list struct. This lets you print the entire list with one println! call. Example: impl fmt::Display for LinkedList { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { let mut current = &self.head; while let Some(node) = current { write!(f, "{} -> ", node.data)?; current = &node.next; } write!(f, "None") } }

Result

Printing the list shows all nodes connected by arrows ending with None.

Using Display trait makes printing cleaner and integrates with Rust's formatting system.

6

Expert

Avoiding Borrowing Pitfalls in Traversal

🤔Before reading on: do you think mutable and immutable borrows can happen simultaneously during traversal? Commit to yes or no.

Concept: Understand Rust's borrowing rules to safely traverse without conflicts.

Rust enforces strict borrowing rules: you cannot have mutable and immutable references to the same data at once. During traversal, if you only read data, use immutable references. If you modify nodes, use mutable references carefully. Example: let mut current = self.head.as_ref(); while let Some(node) = current { println!("{}", node.data); current = node.next.as_ref(); } For mutable traversal, use as_mut() and ensure no other borrows exist.

Result

Traversal code compiles without borrow errors and runs safely.

Mastering borrowing rules prevents common Rust errors and ensures safe memory access during traversal.

Under the Hood

Each node stores a pointer to the next node's memory address. Traversal follows these pointers step-by-step. In Rust, linked lists use Option and Box types to manage ownership and memory safely. The Option type wraps the pointer to handle the end of the list (None). The Box type owns the node on the heap, allowing dynamic memory allocation.

Why designed this way?

Rust's ownership and borrowing rules prevent memory bugs common in linked lists, like dangling pointers or double frees. Using Option and Box enforces safe access and clear ownership. This design trades some complexity for safety and performance.

LinkedList {
  head: Option<Box<Node>>
}

Node {
  data: T,
  next: Option<Box<Node>>
}

Traversal flow:
head -> Node1 -> Node2 -> Node3 -> None

Each arrow is a Box pointer wrapped in Option.

Myth Busters - 4 Common Misconceptions

Quick: Does traversal always require recursion? Commit to yes or no.

Common Belief: Traversal must be done using recursion because linked lists are recursive structures.

Reality: Traversal can be done using simple loops without recursion, which is often more efficient and easier to understand.

Why it matters: Using recursion unnecessarily can cause stack overflow on large lists and complicate code.

Quick: Is it safe to modify a node's next pointer while traversing? Commit to yes or no.

Common Belief: You can freely change next pointers during traversal without issues.

Reality: Modifying next pointers during traversal can break the chain and cause lost nodes or infinite loops if not done carefully.

Why it matters: Incorrect modification leads to corrupted lists and hard-to-find bugs.

Quick: Does printing a linked list always show the data in the order nodes were added? Commit to yes or no.

Common Belief: Printing always shows nodes in the order they were inserted.

Reality: Printing shows nodes in the order they are linked, which may differ from insertion order if nodes were inserted at the front or middle.

Why it matters: Assuming insertion order matches traversal order can cause confusion and incorrect assumptions about data.

Quick: Can you traverse a linked list without knowing the head? Commit to yes or no.

Common Belief: You can start traversal from any node without the head.

Reality: Traversal must start at the head to visit all nodes in order; starting elsewhere misses nodes before that point.

Why it matters: Starting traversal incorrectly leads to incomplete data access.

Expert Zone

1

Traversal performance depends on cache locality; linked lists have poor cache performance compared to arrays.

2

Rust's Option> pattern avoids null pointer bugs common in other languages by making None explicit.

3

Implementing iterators for linked lists allows idiomatic Rust traversal using for loops and iterator methods.

When NOT to use

Linked lists are not ideal when you need fast random access; arrays or vectors are better. For heavy insertions/deletions in the middle, balanced trees or skip lists may outperform linked lists.

Production Patterns

In production Rust code, linked lists are often wrapped in safe abstractions with iterators and Display implementations. They are used when memory allocation patterns or ownership semantics require dynamic, non-contiguous storage.

Connections

Iterators in Rust

Traversal of linked lists builds the foundation for implementing iterators.

Understanding traversal helps create safe, reusable iterator patterns that integrate with Rust's for loops and iterator traits.

Pointers and Memory Management

Linked list traversal relies on following pointers safely.

Knowing how pointers work in memory clarifies why traversal must carefully handle ownership and lifetimes.

Supply Chain Logistics

Traversal is like following a chain of deliveries from start to end.

Seeing traversal as a supply chain helps understand the importance of order and connection in data processing.

Common Pitfalls

#1 Trying to traverse without checking if the list is empty.

Wrong approach:

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

Correct approach:

if head.is_none() {
println!("List is empty");
} else {
let mut current = &head;
while let Some(node) = current {
println!("{}", node.data);
current = &node.next;
}
}

Root cause:

Assuming the list always has nodes leads to unwrap on None, causing runtime panic.

#2 Modifying the list while traversing with immutable references.

Wrong approach:

let mut current = &head;
while let Some(node) = current {
node.next = None; // error: cannot assign to immutable reference
current = &node.next;
}

Correct approach:

let mut current = head.as_mut();
while let Some(node) = current {
node.next = None; // allowed with mutable reference
current = node.next.as_mut();
}

Root cause:

Not understanding Rust's borrowing rules causes compile errors and unsafe code.

#3 Printing nodes without formatting, causing unclear output.

Wrong approach:

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

Correct approach:

impl fmt::Display for LinkedList {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let mut current = &self.head;
while let Some(node) = current {
write!(f, "{} -> ", node.data)?;
current = &node.next;
}
write!(f, "None")
}
}

Root cause:

Not using Rust's formatting traits misses an opportunity for clean, reusable printing.

Key Takeaways

Traversal means visiting each node from the head to the end by following next pointers.

In Rust, traversal uses Option and Box types to safely handle node ownership and absence.

Always check if the list is empty before traversing to avoid runtime errors.

Implementing the Display trait allows clean and idiomatic printing of the entire list.

Understanding Rust's borrowing rules is essential to traverse and modify linked lists safely.

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