Traversal Forward and Backward in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Forward Traversal in Doubly Linked List

What is the printed output of the doubly linked list after inserting nodes 1, 2, and 3 and traversing forward?

DSA Rust

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

struct DoublyLinkedList {
    head: Option<Box<Node>>,
    tail: Option<*mut Node>,
}

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

    fn append(&mut self, data: i32) {
        let mut new_node = Box::new(Node { data, next: None, prev: None });
        let raw_new: *mut _ = &mut *new_node;

        match self.tail {
            None => {
                self.head = Some(new_node);
                self.tail = Some(raw_new);
            }
            Some(tail) => unsafe {
                (*tail).next = Some(new_node);
                (*raw_new).prev = Some(tail);
                self.tail = Some(raw_new);
            },
        }
    }

    fn traverse_forward(&self) {
        let mut current = self.head.as_ref();
        while let Some(node) = current {
            print!("{} -> ", node.data);
            current = node.next.as_ref();
        }
        print!("null");
    }
}

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

A 1 -> 2 -> 3 -> null

B 3 -> 2 -> 1 -> null

C 1 -> 3 -> 2 -> null

D null -> 1 -> 2 -> 3

💡 Hint

Think about how nodes are appended and how traversal moves from head to tail.

The append method adds nodes at the end. Traversing forward starts at head and moves through next pointers, printing 1, then 2, then 3, then null.

❓ Predict Output

intermediate

Output of Backward Traversal in Doubly Linked List

What is the printed output of the doubly linked list after inserting nodes 1, 2, and 3 and traversing backward?

DSA Rust

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

struct DoublyLinkedList {
    head: Option<Box<Node>>,
    tail: Option<*mut Node>,
}

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

    fn append(&mut self, data: i32) {
        let mut new_node = Box::new(Node { data, next: None, prev: None });
        let raw_new: *mut _ = &mut *new_node;

        match self.tail {
            None => {
                self.head = Some(new_node);
                self.tail = Some(raw_new);
            }
            Some(tail) => unsafe {
                (*tail).next = Some(new_node);
                (*raw_new).prev = Some(tail);
                self.tail = Some(raw_new);
            },
        }
    }

    fn traverse_backward(&self) {
        let mut current = self.tail;
        while let Some(node_ptr) = current {
            unsafe {
                print!("{} -> ", (*node_ptr).data);
                current = (*node_ptr).prev;
            }
        }
        print!("null");
    }
}

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

A null -> 3 -> 2 -> 1

B 1 -> 2 -> 3 -> null

C 2 -> 3 -> 1 -> null

D 3 -> 2 -> 1 -> null

💡 Hint

Backward traversal starts from tail and moves through prev pointers.

The backward traversal prints nodes starting from tail (3), then 2, then 1, then null.

🔧 Debug

advanced

Identify the Error in Backward Traversal

What error will this Rust code produce when trying to traverse backward in a doubly linked list?

DSA Rust

fn traverse_backward(&self) {
    let mut current = self.tail;
    while let Some(node_ptr) = current {
        print!("{} -> ", (*node_ptr).data);
        current = (*node_ptr).prev.unwrap();
    }
    print!("null");
}

A Runtime panic: unwrap on None value

B SyntaxError: missing unsafe block

C TypeError: cannot dereference raw pointer

D No error, prints backward traversal correctly

💡 Hint

Dereferencing raw pointers in Rust requires a special block.

Dereferencing raw pointers (*node_ptr) must be inside an unsafe block. Missing unsafe causes a compile-time error.

❓ Predict Output

advanced

Output After Mixed Forward and Backward Traversal

Given the doubly linked list with nodes 10, 20, 30 appended, what is the output of traversing forward then backward?

DSA Rust

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

struct DoublyLinkedList {
    head: Option<Box<Node>>,
    tail: Option<*mut Node>,
}

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

    fn append(&mut self, data: i32) {
        let mut new_node = Box::new(Node { data, next: None, prev: None });
        let raw_new: *mut _ = &mut *new_node;

        match self.tail {
            None => {
                self.head = Some(new_node);
                self.tail = Some(raw_new);
            }
            Some(tail) => unsafe {
                (*tail).next = Some(new_node);
                (*raw_new).prev = Some(tail);
                self.tail = Some(raw_new);
            },
        }
    }

    fn traverse_forward(&self) {
        let mut current = self.head.as_ref();
        while let Some(node) = current {
            print!("{} -> ", node.data);
            current = node.next.as_ref();
        }
    }

    fn traverse_backward(&self) {
        let mut current = self.tail;
        while let Some(node_ptr) = current {
            unsafe {
                print!("{} -> ", (*node_ptr).data);
                current = (*node_ptr).prev;
            }
        }
    }
}

fn main() {
    let mut list = DoublyLinkedList::new();
    list.append(10);
    list.append(20);
    list.append(30);
    list.traverse_forward();
    print!("null -> ");
    list.traverse_backward();
    print!("null");
}

A 10 -> 20 -> 30 -> null -> 30 -> 20 -> 10 -> null

B 30 -> 20 -> 10 -> null -> 10 -> 20 -> 30 -> null

C 10 -> 20 -> 30 -> 30 -> 20 -> 10 -> null -> null

D null -> 10 -> 20 -> 30 -> null -> 30 -> 20 -> 10

💡 Hint

Forward traversal prints from head to tail, backward from tail to head.

First prints 10, 20, 30, then null, then backward prints 30, 20, 10, then null.

🧠 Conceptual

expert

Why Use Raw Pointers for Prev in Rust Doubly Linked List?

In Rust, why is the 'prev' pointer in a doubly linked list often declared as a raw pointer (*mut Node) instead of a Box or Option>?

A Because Rust does not allow Option<Box<Node>> types in structs due to size constraints.

B Because Box pointers are slower and raw pointers improve performance significantly.

C Because raw pointers allow mutable aliasing which Box does not, enabling backward links without ownership conflicts.

D Because raw pointers automatically manage memory freeing unlike Box pointers.

💡 Hint

Think about Rust's ownership rules and how backward links can cause multiple owners.

Rust's ownership rules prevent multiple owners of the same data. Using Box for prev would cause ownership conflicts. Raw pointers allow mutable aliasing without ownership, but require unsafe code.

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