Traversal Forward and Backward in DSA Rust - Execution Trace

Concept Flow - Traversal Forward and Backward

Start at Head Node

↓

Visit Current Node

→Move to Next Node?

| Yes↓

Repeat Visit

No↓

Reached Tail Node

↓

Visit Tail Node

↓

Move Back to Previous Node?

| Yes↓

Repeat Visit Backward

No↓

Traversal Complete

Start from the head node, move forward visiting each node until the tail, then move backward visiting nodes until reaching the head again.

Execution Sample

DSA Rust

let mut current = head;
while let Some(node) = current {
    print!("{} -> ", node.value);
    current = node.next.as_ref();
}
// Then backward traversal
let mut tail = tail;
while let Some(node) = tail {
    print!("{} -> ", node.value);
    tail = node.prev.as_ref();
}

Traverse a doubly linked list forward from head to tail, then backward from tail to head, printing node values.

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Start at head	Node 1	current = Node 1	1 <-> 2 <-> 3 <-> 4 <-> 5
2	Visit Node 1	Node 1	Print 1	1 <-> 2 <-> 3 <-> 4 <-> 5
3	Move forward	Node 2	current = Node 2	1 <-> 2 <-> 3 <-> 4 <-> 5
4	Visit Node 2	Node 2	Print 2	1 <-> 2 <-> 3 <-> 4 <-> 5
5	Move forward	Node 3	current = Node 3	1 <-> 2 <-> 3 <-> 4 <-> 5
6	Visit Node 3	Node 3	Print 3	1 <-> 2 <-> 3 <-> 4 <-> 5
7	Move forward	Node 4	current = Node 4	1 <-> 2 <-> 3 <-> 4 <-> 5
8	Visit Node 4	Node 4	Print 4	1 <-> 2 <-> 3 <-> 4 <-> 5
9	Move forward	Node 5	current = Node 5	1 <-> 2 <-> 3 <-> 4 <-> 5
10	Visit Node 5	Node 5	Print 5	1 <-> 2 <-> 3 <-> 4 <-> 5
11	Forward traversal ends	None	current = None	1 <-> 2 <-> 3 <-> 4 <-> 5
12	Start backward at tail	Node 5	tail = Node 5	1 <-> 2 <-> 3 <-> 4 <-> 5
13	Visit Node 5	Node 5	Print 5	1 <-> 2 <-> 3 <-> 4 <-> 5
14	Move backward	Node 4	tail = Node 4	1 <-> 2 <-> 3 <-> 4 <-> 5
15	Visit Node 4	Node 4	Print 4	1 <-> 2 <-> 3 <-> 4 <-> 5
16	Move backward	Node 3	tail = Node 3	1 <-> 2 <-> 3 <-> 4 <-> 5
17	Visit Node 3	Node 3	Print 3	1 <-> 2 <-> 3 <-> 4 <-> 5
18	Move backward	Node 2	tail = Node 2	1 <-> 2 <-> 3 <-> 4 <-> 5
19	Visit Node 2	Node 2	Print 2	1 <-> 2 <-> 3 <-> 4 <-> 5
20	Move backward	Node 1	tail = Node 1	1 <-> 2 <-> 3 <-> 4 <-> 5
21	Visit Node 1	Node 1	Print 1	1 <-> 2 <-> 3 <-> 4 <-> 5
22	Backward traversal ends	None	tail = None	1 <-> 2 <-> 3 <-> 4 <-> 5

💡 Traversal stops when current or tail pointer becomes None, indicating end of list in forward or backward direction.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 9	After Step 11	After Step 14	After Step 16	After Step 18	After Step 20	After Step 22
current	Node 1	Node 2	Node 3	Node 4	Node 5	None	None	None	None	None	None
tail	None	None	None	None	None	None	Node 4	Node 3	Node 2	Node 1	None

Key Moments - 3 Insights

Why does the forward traversal stop when current becomes None?

Because current points to the next node each time, when it reaches None, it means there is no next node left to visit. See execution_table row 11.

Why do we need a tail pointer for backward traversal?

Backward traversal starts from the tail node, which is the last node in the list. Without tail, we cannot move backward. See execution_table row 12.

Why do we print the node value before moving the pointer?

We print the current node's value first to visit it, then move the pointer to the next or previous node. This order ensures all nodes are visited. See execution_table rows 2,4,6,... and 13,15,17,...

Visual Quiz - 3 Questions

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

A Node 3

B Node 2

C Node 4

D Node 5

💡 Hint

Check the 'current' variable in variable_tracker after step 7.

At which step does the forward traversal end?

A Step 11

B Step 10

C Step 12

D Step 22

💡 Hint

Look for the step where 'current' becomes None in execution_table.

If the list had only 3 nodes, how would the backward traversal steps change?

A Backward traversal would not happen

B Backward traversal would start at Node 3 and end at Node 1 in fewer steps

C Backward traversal would start at Node 1

D Backward traversal would print nodes twice

💡 Hint

Think about how traversal depends on list length shown in execution_table visual state.

Concept Snapshot

Traversal Forward and Backward in Doubly Linked List:
- Start at head, visit nodes moving next until tail
- Then start at tail, visit nodes moving prev until head
- Use 'current' pointer for forward, 'tail' pointer for backward
- Stop when pointer becomes None
- Print node values during visits

Full Transcript

Traversal forward and backward in a doubly linked list means visiting each node from the start to the end, then back from the end to the start. We begin at the head node and move forward using the next pointers, printing each node's value. When we reach the end (current pointer becomes None), forward traversal stops. Then we start backward traversal from the tail node, moving backward using the prev pointers, printing each node's value until we reach the start (tail pointer becomes None). This process ensures all nodes are visited in both directions. The pointers current and tail track our position during traversal. The traversal stops when these pointers become None, indicating no more nodes to visit in that direction.

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