Traversal Forward and Backward in DSA Rust

Mental Model

Traversal means visiting each item in a list one by one, either from start to end or from end to start.

Analogy: Imagine walking down a row of houses on a street, first going from the first house to the last (forward), then walking back from the last house to the first (backward).

head -> 1 ↔ 2 ↔ 3 ↔ 4 -> null
↑current at head

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3 ↔ 4, traverse forward then backward

Goal: Visit all nodes from start to end, then from end back to start, printing their values

Step 1: start at head node with value 1

head -> [curr->1] ↔ 2 ↔ 3 ↔ 4 -> null

Why: We begin traversal from the first node

Step 2: visit node 1 and move curr forward to node 2

head -> 1 ↔ [curr->2] ↔ 3 ↔ 4 -> null

Why: We visit nodes in order moving forward

Step 3: visit node 2 and move curr forward to node 3

head -> 1 ↔ 2 ↔ [curr->3] ↔ 4 -> null

Why: Continue forward traversal

Step 4: visit node 3 and move curr forward to node 4

head -> 1 ↔ 2 ↔ 3 ↔ [curr->4] -> null

Why: Continue forward traversal

Step 5: visit node 4; curr forward is null, stop forward traversal

head -> 1 ↔ 2 ↔ 3 ↔ 4 -> [curr->null]

Why: Reached end of list

Step 6: start backward traversal from node 4

head -> 1 ↔ 2 ↔ 3 ↔ [curr->4] -> null

Why: We now visit nodes backward from the last node

Step 7: visit node 4 and move curr backward to node 3

head -> 1 ↔ 2 ↔ [curr->3] ↔ 4 -> null

Why: Move backward visiting nodes

Step 8: visit node 3 and move curr backward to node 2

head -> 1 ↔ [curr->2] ↔ 3 ↔ 4 -> null

Why: Continue backward traversal

Step 9: visit node 2 and move curr backward to node 1

head -> [curr->1] ↔ 2 ↔ 3 ↔ 4 -> null

Why: Continue backward traversal

Step 10: visit node 1; curr backward is null, stop backward traversal

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

Why: Reached start of list

Result:

Forward traversal: 1 -> 2 -> 3 -> 4 -> null
Backward traversal: 4 -> 3 -> 2 -> 1 -> null

Annotated Code

DSA Rust

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

#[derive(Debug)]
struct Node {
    val: i32,
    next: Option<Rc<RefCell<Node>>>,
    prev: Option<Rc<RefCell<Node>>>,
}

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

struct DoublyLinkedList {
    head: Option<Rc<RefCell<Node>>>,
    tail: Option<Rc<RefCell<Node>>>,
}

impl DoublyLinkedList {
    fn new() -> Self {
        DoublyLinkedList { head: None, tail: None }
    }

    fn append(&mut self, val: i32) {
        let new_node = Node::new(val);
        match self.tail.take() {
            Some(old_tail) => {
                old_tail.borrow_mut().next = Some(new_node.clone()); // link old tail to new node
                new_node.borrow_mut().prev = Some(old_tail.clone()); // link new node back to old tail
                self.tail = Some(new_node);
            }
            None => {
                self.head = Some(new_node.clone());
                self.tail = Some(new_node);
            }
        }
    }

    fn traverse_forward(&self) {
        let mut curr = self.head.clone();
        while let Some(node) = curr {
            print!("{} -> ", node.borrow().val); // print current node value
            curr = node.borrow().next.clone(); // move forward
        }
        println!("null");
    }

    fn traverse_backward(&self) {
        let mut curr = self.tail.clone();
        while let Some(node) = curr {
            print!("{} -> ", node.borrow().val); // print current node value
            curr = node.borrow().prev.clone(); // move backward
        }
        println!("null");
    }
}

fn main() {
    let mut list = DoublyLinkedList::new();
    list.append(1);
    list.append(2);
    list.append(3);
    list.append(4);

    print!("Forward traversal: ");
    list.traverse_forward();

    print!("Backward traversal: ");
    list.traverse_backward();
}

old_tail.borrow_mut().next = Some(new_node.clone()); // link old tail to new node

connect previous last node forward to new node

new_node.borrow_mut().prev = Some(old_tail.clone()); // link new node back to old tail

connect new node backward to previous last node

curr = node.borrow().next.clone(); // move forward

advance current pointer forward during forward traversal

curr = node.borrow().prev.clone(); // move backward

advance current pointer backward during backward traversal

Output

Forward traversal: 1 -> 2 -> 3 -> 4 -> null

Backward traversal: 4 -> 3 -> 2 -> 1 -> null

Complexity Analysis

Time: O(n) because we visit each of the n nodes once in forward and once in backward traversal

Space: O(n) because we store n nodes in the doubly linked list

vs Alternative: Compared to singly linked list, backward traversal is not possible without extra memory or reversing the list, so doubly linked list allows efficient backward traversal

Edge Cases

empty list

traversal prints only 'null' since no nodes exist

DSA Rust

while let Some(node) = curr {

single node list

forward and backward traversal both print the single node value followed by null

DSA Rust

while let Some(node) = curr {

When to Use This Pattern

When you need to visit elements in both directions efficiently, use a doubly linked list and traverse forward and backward using next and prev pointers.

Common Mistakes

Mistake: Trying to traverse backward in a singly linked list without extra memory
Fix: Use a doubly linked list that stores backward pointers (prev) to enable backward traversal

Mistake: Not cloning Rc pointers when moving curr, causing ownership errors
Fix: Clone Rc pointers when moving curr to keep ownership and avoid borrow errors

Summary

It visits each node in a doubly linked list from start to end and then from end back to start.

Use it when you want to see all elements in order and also in reverse order efficiently.

The key is that each node knows both its next and previous neighbors, so you can move forward or backward easily.

Practice

1. What does "Traversal Forward and Backward" mean in the context of a doubly linked list?

easy

A. Skipping nodes while moving forward

B. Moving through the list from the first node to the last and then back from the last to the first

C. Only moving from the first node to the last node

D. Moving randomly between nodes

Solution

1. Step 1: Understand doubly linked list structure

   A doubly linked list has nodes connected both forward and backward, allowing movement in both directions.

2. Step 2: Define traversal forward and backward

   Traversal forward means moving from the first node to the last node, and traversal backward means moving from the last node back to the first node.

3. Final Answer:

   Moving through the list from the first node to the last and then back from the last to the first -> Option B

4. Quick Check:

   Forward and backward traversal = Moving both ways [OK]

Hint: Think of walking to the end and then returning back [OK]

Common Mistakes:

• Confusing traversal with skipping nodes
• Thinking traversal is only forward
• Assuming random movement is traversal

2. Which of the following Rust code snippets correctly traverses a doubly linked list forward using a mutable reference?

easy

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

B. while let Some(node) = current { println!("{}", node.value); current = node.prev.as_deref_mut(); }

C. while let Some(node) = current { println!("{}", node.value); current = node.next.as_deref_mut(); }

D. loop { println!("{}", current.value); current = current.prev; }

Solution

1. Step 1: Identify forward traversal in Rust

   Forward traversal moves from current node to next node using the next pointer.

2. Step 2: Check code correctness

   while let Some(node) = current { println!("{}", node.value); current = node.next.as_deref_mut(); } uses current = node.next.as_deref_mut() which correctly moves forward. while let Some(node) = current { println!("{}", node.value); current = node.prev.as_deref_mut(); } moves backward, C is invalid syntax for linked list, D loops backward without condition.

3. Final Answer:

   while let Some(node) = current { println!("{}", node.value); current = node.next.as_deref_mut(); } -> Option C

4. Quick Check:

   Forward traversal uses next pointer [OK]

Hint: Forward traversal uses next pointer, backward uses prev [OK]

Common Mistakes:

• Using prev pointer for forward traversal
• Incorrect loop syntax for linked list
• Ignoring option handling in Rust

3. Given the following Rust code for a doubly linked list traversal backward, what will be printed?

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

fn traverse_backward(mut current: Option<&Node>) {
    while let Some(node) = current {
        print!("{} ", node.value);
        current = node.prev.as_deref();
    }
}

// Assume list nodes with values 1 -> 2 -> 3, current starts at node with value 3

medium

A. 3 2 1

B. 1 2 3

C. 3 1 2

D. 1 3 2

Solution

1. Step 1: Understand backward traversal

   Starting at node with value 3, moving backward means following prev pointers to 2, then 1.

2. Step 2: Trace the print output

   Prints 3 first, then 2, then 1, each followed by a space.

3. Final Answer:

   3 2 1 -> Option A

4. Quick Check:

   Backward traversal prints nodes in reverse order [OK]

Hint: Backward traversal prints nodes from tail to head [OK]

Common Mistakes:

• Confusing forward and backward order
• Assuming traversal starts at head
• Ignoring Option handling in Rust

4. Identify the error in the following Rust code snippet that attempts to traverse a doubly linked list forward:

fn traverse(mut current: Option<&Node>) {
    while current.is_some() {
        println!("{}", current.unwrap().value);
        current = current.unwrap().next.as_deref();
    }
}

medium

A. The loop condition should be while current.is_none()

B. println! macro syntax is incorrect

C. next pointer should be accessed with prev instead

D. Using unwrap() multiple times causes panic if current is None

Solution

1. Step 1: Analyze unwrap() usage

   Calling unwrap() twice without checking can panic if current becomes None between calls.

2. Step 2: Suggest safer approach

   Use while let Some(node) = current to safely unwrap once per iteration.

3. Final Answer:

   Using unwrap() multiple times causes panic if current is None -> Option D

4. Quick Check:

   Multiple unwrap() calls risk panic [OK]

Hint: Use while let Some(node) = current to avoid unwrap panic [OK]

Common Mistakes:

• Confusing is_some() and is_none()
• Accessing wrong pointer for forward traversal
• Misusing println! macro

5. You have a doubly linked list with nodes containing values [10, 20, 30, 40]. Write a Rust function that traverses forward to collect values into a vector, then traverses backward from the last node to collect values into another vector. What will be the content of both vectors after traversal?

hard

A. Forward: [10, 20, 30, 40], Backward: [40, 30, 20, 10]

B. Forward: [40, 30, 20, 10], Backward: [10, 20, 30, 40]

C. Forward: [10, 20, 30], Backward: [40, 30, 20]

D. Forward: [], Backward: []

Solution

1. Step 1: Traverse forward collecting values

   Starting at head (10), collect values in order: 10, 20, 30, 40.

2. Step 2: Traverse backward from last node collecting values

   Starting at tail (40), collect values backward: 40, 30, 20, 10.

3. Final Answer:

   Forward: [10, 20, 30, 40], Backward: [40, 30, 20, 10] -> Option A

4. Quick Check:

   Forward and backward vectors match traversal order [OK]

Hint: Forward collects from head to tail, backward from tail to head [OK]

Common Mistakes:

• Mixing order of forward and backward vectors
• Missing last node in traversal
• Confusing vector contents with node pointers