Traversal Forward and Backward in DSA Typescript - Execution Trace

Concept Flow - Traversal Forward and Backward

Start at Head Node

↓

Visit Current Node

↓

Move Forward: current = current.next

↓

Is current null?

No→Repeat Visit

Yes↓

Reached Tail Node

↓

Visit Current Node

↓

Move Backward: current = current.prev

↓

Is current null?

No→Repeat Visit

Yes↓

Traversal Complete

Traverse nodes from head to tail using next pointers, then from tail to head using prev pointers.

Execution Sample

DSA Typescript

class Node {
  constructor(public val: number, public next: Node | null = null, public prev: Node | null = null) {}
}

// Assuming head and tail are defined and point to the first and last nodes respectively
let current = head;
while(current) { console.log(current.val); current = current.next; }
current = tail;
while(current) { console.log(current.val); current = current.prev; }

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 Value	Pointer Changes	Visual State
1	Start at head	1	current = head (Node 1)	1 <-> 2 <-> 3 <-> 4 <-> 5
2	Visit current node	1	None	1 <-> 2 <-> 3 <-> 4 <-> 5
3	Move forward	2	current = current.next (Node 2)	1 <-> 2 <-> 3 <-> 4 <-> 5
4	Visit current node	2	None	1 <-> 2 <-> 3 <-> 4 <-> 5
5	Move forward	3	current = current.next (Node 3)	1 <-> 2 <-> 3 <-> 4 <-> 5
6	Visit current node	3	None	1 <-> 2 <-> 3 <-> 4 <-> 5
7	Move forward	4	current = current.next (Node 4)	1 <-> 2 <-> 3 <-> 4 <-> 5
8	Visit current node	4	None	1 <-> 2 <-> 3 <-> 4 <-> 5
9	Move forward	5	current = current.next (Node 5)	1 <-> 2 <-> 3 <-> 4 <-> 5
10	Visit current node	5	None	1 <-> 2 <-> 3 <-> 4 <-> 5
11	Move forward	null	current = current.next (null)	1 <-> 2 <-> 3 <-> 4 <-> 5
12	Reached tail, start backward traversal	5	current = tail (Node 5)	1 <-> 2 <-> 3 <-> 4 <-> 5
13	Visit current node	5	None	1 <-> 2 <-> 3 <-> 4 <-> 5
14	Move backward	4	current = current.prev (Node 4)	1 <-> 2 <-> 3 <-> 4 <-> 5
15	Visit current node	4	None	1 <-> 2 <-> 3 <-> 4 <-> 5
16	Move backward	3	current = current.prev (Node 3)	1 <-> 2 <-> 3 <-> 4 <-> 5
17	Visit current node	3	None	1 <-> 2 <-> 3 <-> 4 <-> 5
18	Move backward	2	current = current.prev (Node 2)	1 <-> 2 <-> 3 <-> 4 <-> 5
19	Visit current node	2	None	1 <-> 2 <-> 3 <-> 4 <-> 5
20	Move backward	1	current = current.prev (Node 1)	1 <-> 2 <-> 3 <-> 4 <-> 5
21	Visit current node	1	None	1 <-> 2 <-> 3 <-> 4 <-> 5
22	Move backward	null	current = current.prev (null)	1 <-> 2 <-> 3 <-> 4 <-> 5
23	Traversal complete	null	current is null, stop	1 <-> 2 <-> 3 <-> 4 <-> 5

💡 Traversal stops when current becomes null moving forward and backward.

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	Final
current	Node 1	Node 2	Node 3	Node 4	Node 5	null	Node 4	Node 3	Node 2	Node 1	null	null

Key Moments - 3 Insights

Why do we check if current is null to stop traversal?

Because when current becomes null, it means we have moved past the last node (forward) or before the first node (backward), so traversal must stop. See execution_table steps 11 and 22.

Why do we start backward traversal from tail, not head?

Backward traversal uses prev pointers, so starting at tail ensures we visit nodes in reverse order. See execution_table step 12 where current is set to tail.

Does the list structure change during traversal?

No, traversal only moves the current pointer; the list nodes and their connections remain unchanged. Visual state stays the same in all steps.

Visual Quiz - 3 Questions

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

A Node with value 3

B Node with value 4

C Node with value 2

D null

💡 Hint

Check the 'Pointer Changes' and 'Current Node Value' columns at step 7.

At which step does the forward traversal end?

A Step 11

B Step 12

C Step 10

D Step 9

💡 Hint

Look for when current becomes null moving forward in the execution_table.

If the list had only one node, how many times would the backward traversal visit nodes?

A Zero times

B Two times

C One time

D Three times

💡 Hint

Refer to variable_tracker and execution_table steps for backward traversal starting at tail.

Concept Snapshot

Traversal Forward and Backward in Doubly Linked List:
- Start at head, visit nodes moving next until null
- Then start at tail, visit nodes moving prev until null
- current pointer moves, list structure unchanged
- Stops when current is null
- Useful to access all nodes in both directions

Full Transcript

This concept shows how to traverse a doubly linked list forward from head to tail using next pointers, then backward from tail to head using prev pointers. We start with current at head, visit each node, then move current to next until it becomes null, signaling end of forward traversal. Then we set current to tail and move backward visiting nodes using prev pointers until current is null again. The list structure remains unchanged during traversal. This allows visiting all nodes in order and reverse order easily.

Practice

1. What does forward traversal in a linked list mean?

easy

A. Visiting nodes randomly without order

B. Visiting nodes from the tail to the head in order

C. Skipping every other node while traversing

D. Visiting nodes from the head to the tail in order

Solution

1. Step 1: Understand linked list structure

   A linked list has nodes connected from head to tail in one direction.

2. Step 2: Define forward traversal

   Forward traversal means visiting nodes starting at the head and moving to the tail in order.

3. Final Answer:

   Visiting nodes from the head to the tail in order -> Option D

4. Quick Check:

   Forward traversal = head to tail [OK]

Hint: Forward means start at head and go next nodes [OK]

Common Mistakes:

• Confusing forward with backward traversal
• Thinking traversal is random
• Assuming skipping nodes is traversal

2. Which TypeScript syntax correctly traverses an array forward using a for loop?

easy

A. for(let i = arr.length; i >= 0; i--) { console.log(arr[i]); }

B. for(let i = 0; i < arr.length; i++) { console.log(arr[i]); }

C. for(let i = 1; i <= arr.length; i++) { console.log(arr[i]); }

D. for(let i = arr.length - 1; i > 0; i--) { console.log(arr[i]); }

Solution

1. Step 1: Identify forward traversal loop

   Forward traversal starts at index 0 and goes up to length-1.

2. Step 2: Check loop conditions

   for(let i = 0; i < arr.length; i++) { console.log(arr[i]); } loops from 0 to less than arr.length, printing each element correctly.

3. Final Answer:

   for(let i = 0; i < arr.length; i++) { console.log(arr[i]); } -> Option B

4. Quick Check:

   Forward loop index from 0 to length-1 [OK]

Hint: Start index 0, end before length for forward loop [OK]

Common Mistakes:

• Starting index at 1 instead of 0
• Using i <= arr.length causing out-of-bounds
• Looping backward for forward traversal

3. What is the output of this TypeScript code?

const arr = [10, 20, 30];
for(let i = arr.length - 1; i >= 0; i--) {
  console.log(arr[i]);
}

medium

A. 30 20 10

B. 10 20 30

C. 30 20

D. Error: Index out of bounds

Solution

1. Step 1: Understand loop start and end

   The loop starts at index 2 (arr.length - 1) and goes down to 0.

2. Step 2: Trace output values

   It prints arr[2] = 30, arr[1] = 20, arr[0] = 10 in that order.

3. Final Answer:

   30 20 10 -> Option A

4. Quick Check:

   Backward traversal prints 30 20 10 [OK]

Hint: Backward loop starts at length-1 down to 0 [OK]

Common Mistakes:

• Thinking output is forward order
• Missing last element at index 0
• Assuming error due to loop

4. Identify the error in this backward traversal code for a linked list:

let current = head;
while(current !== null) {
  console.log(current.value);
  current = current.prev;
}

medium

A. It should use current.next instead of current.prev

B. No error, code is correct

C. It should start from tail, not head

D. It should check current.next !== null in while condition

Solution

1. Step 1: Understand backward traversal in linked list

   Backward traversal uses prev pointers starting from the tail node.

2. Step 2: Check starting node

   The code starts at head, but to go backward, it must start at tail.

3. Final Answer:

   It should start from tail, not head -> Option C

4. Quick Check:

   Backward traversal starts at tail [OK]

Hint: Backward traversal must start at tail node [OK]

Common Mistakes:

• Starting backward traversal at head
• Using next instead of prev for backward
• Wrong loop condition check

5. Given a doubly linked list, how would you print all values backward starting from the head node?

hard

A. Traverse forward to tail, then traverse backward from tail to head

B. Traverse backward directly from head using prev pointers

C. Use only next pointers starting from head to print backward

D. Reverse the list first, then traverse forward

Solution

1. Step 1: Understand doubly linked list structure

   Each node has next and prev pointers; head has no prev, tail has no next.

2. Step 2: Plan backward print from head

   To print backward from head, first move forward to tail using next pointers.

3. Step 3: Traverse backward from tail

   From tail, use prev pointers to print nodes backward to head.

4. Final Answer:

   Traverse forward to tail, then traverse backward from tail to head -> Option A

5. Quick Check:

   Backward print from head requires forward then backward traversal [OK]

Hint: Go forward to tail, then backward to print [OK]

Common Mistakes:

• Trying to go backward directly from head
• Using next pointers to print backward
• Reversing list unnecessarily