Traversal Forward and Backward in DSA Javascript - Execution Trace

Concept Flow - Traversal Forward and Backward

Start at head node

↓

Visit current node

↓

Move to next node

↓

Is next node null?

Yes→Stop forward traversal

No↓

Repeat forward traversal

↓

At last node, start backward traversal

↓

Visit current node

↓

Move to previous node

↓

Is previous node null?

Yes→Stop backward traversal

No↓

Repeat backward traversal

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

Execution Sample

DSA Javascript

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

// Traverse forward and backward
function traverse(head, tail) {
  let current = head;
  // Forward traversal
  while (current !== null) {
    console.log(current.value);
    current = current.next;
  }
  // Backward traversal
  current = tail;
  while (current !== null) {
    console.log(current.value);
    current = current.prev;
  }
}

This code defines a doubly linked list node and shows traversal forward and backward.

Execution Table

Step	Operation	Current Node Value	Pointer Changes	Visual State
1	Start at head	1	head points to Node(1)	1 <-> 2 <-> 3 <-> null
2	Visit current node	1	none	1 <-> 2 <-> 3 <-> null
3	Move to next node	2	current moves to Node(2)	1 <-> 2 <-> 3 <-> null
4	Visit current node	2	none	1 <-> 2 <-> 3 <-> null
5	Move to next node	3	current moves to Node(3)	1 <-> 2 <-> 3 <-> null
6	Visit current node	3	none	1 <-> 2 <-> 3 <-> null
7	Move to next node	null	current moves to null (end)	1 <-> 2 <-> 3 <-> null
8	Start backward traversal at tail	3	current points to Node(3)	1 <-> 2 <-> 3 <-> null
9	Visit current node	3	none	1 <-> 2 <-> 3 <-> null
10	Move to previous node	2	current moves to Node(2)	1 <-> 2 <-> 3 <-> null
11	Visit current node	2	none	1 <-> 2 <-> 3 <-> null
12	Move to previous node	1	current moves to Node(1)	1 <-> 2 <-> 3 <-> null
13	Visit current node	1	none	1 <-> 2 <-> 3 <-> null
14	Move to previous node	null	current moves to null (start)	1 <-> 2 <-> 3 <-> null
15	Traversal complete	null	no more nodes	Traversal ends

💡 Traversal stops when current pointer moves to null in both forward and backward directions.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 10	After Step 12	After Step 14	Final
current	Node(1)	Node(2)	Node(3)	null	Node(2)	Node(1)	null	null
head	Node(1)	Node(1)	Node(1)	Node(1)	Node(1)	Node(1)	Node(1)	Node(1)
tail	Node(3)	Node(3)	Node(3)	Node(3)	Node(3)	Node(3)	Node(3)	Node(3)

Key Moments - 3 Insights

Why does the forward traversal stop when current becomes null?

Because the last node's next pointer is null, indicating no more nodes ahead. See execution_table step 7 where current moves to null and traversal stops.

How do we know where to start backward traversal?

Backward traversal starts at the tail node, which is the last node visited in forward traversal. See execution_table step 8 where current points to Node(3) to begin backward traversal.

Why do we check for previous pointer being null in backward traversal?

Because the first node's previous pointer is null, meaning no nodes before it. See execution_table step 14 where current moves to null and backward traversal ends.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of current node at step 5?

A 1

B 2

C 3

D null

💡 Hint

Check the 'Current Node Value' column at step 5 in execution_table.

At which step does the forward traversal end?

A Step 6

B Step 7

C Step 8

D Step 9

💡 Hint

Look for when current moves to null in forward traversal in execution_table.

If the list had only one node, how many steps would the forward traversal take before stopping?

A 1

B 2

C 3

D 4

💡 Hint

Think about visiting the single node and then moving to next which is null.

Concept Snapshot

Traversal Forward and Backward in doubly linked list:
- Start at head, visit nodes using next pointers until null
- Then start at tail, visit nodes using prev pointers until null
- Stops when current pointer is null
- Allows visiting all nodes in both directions
- Useful for bidirectional data access

Full Transcript

Traversal forward and backward means visiting nodes in a doubly linked list first from head to tail using next pointers, then from tail to head using previous pointers. We start at the head node, visit it, then move to the next node repeatedly until we reach null, which means the end. Then we start backward traversal at the tail node, visit it, and move to previous nodes until we reach null again, which means the start. This way, we can see all nodes in order both ways. The execution table shows each step, current node value, pointer changes, and the visual state of the list. The variable tracker shows how the current pointer moves forward and backward. Key moments clarify why traversal stops at null pointers and how backward traversal starts at the tail. The visual quiz tests understanding of current node values and traversal stopping points. This method is important for data structures that allow two-way navigation.

Practice

1. What does it mean to traverse a linked list forward?

easy

A. Visiting nodes randomly without order

B. Visiting nodes from the first node to the last node in order

C. Skipping every other node while visiting

D. Visiting nodes from the last node to the first node in reverse order

Solution

1. Step 1: Understand forward traversal

   Forward traversal means starting at the first node (head) and moving to the next node repeatedly until the end.

2. Step 2: Compare with other options

   Backward traversal is the opposite, from last to first. Skipping or random visiting is not traversal.

3. Final Answer:

   Visiting nodes from the first node to the last node in order -> Option B

4. Quick Check:

   Forward traversal = first to last [OK]

Hint: Forward means start to end in order [OK]

Common Mistakes:

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

2. Which of the following is the correct syntax to traverse an array arr forward in JavaScript?

easy

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

B. for (let i = arr.length; i >= 0; 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 syntax

   Forward traversal starts at index 0 and goes up to index arr.length - 1, so i from 0 to less than arr.length.

2. Step 2: Check each option

   for (let i = 0; i < arr.length; i++) { console.log(arr[i]); } uses i = 0 to i < arr.length, correct. for (let i = arr.length; i >= 0; i--) { console.log(arr[i]); } and D count backward. for (let i = 1; i <= arr.length; i++) { console.log(arr[i]); } starts at 1 and accesses arr[arr.length], which is undefined.

3. Final Answer:

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

4. Quick Check:

   Forward array loop = i from 0 to length-1 [OK]

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

Common Mistakes:

• Starting loop at 1 instead of 0
• Using <= instead of < in loop condition
• Looping backward for forward traversal

3. What will be the output of the following code?

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

medium

A. 10 20 30

B. undefined undefined undefined

C. 30 20 10

D. SyntaxError

Solution

1. Step 1: Analyze loop indices

   The loop starts at i = arr.length - 1 = 2, then decrements i until 0, so indices 2, 1, 0.

2. Step 2: Print elements in reverse order

   arr[2] = 30, arr[1] = 20, arr[0] = 10, so output is 30 20 10.

3. Final Answer:

   30 20 10 -> Option C

4. Quick Check:

   Backward loop prints elements in reverse [OK]

Hint: Loop backward from length-1 to 0 for reverse output [OK]

Common Mistakes:

• Confusing forward and backward indices
• Expecting output in original order
• Off-by-one errors in loop condition

4. Identify the error in the following backward traversal code for an array nums:

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

medium

A. No error, code is correct

B. Loop should increment i instead of decrement

C. Loop condition should be i <= nums.length

D. Loop should start at nums.length - 1 and decrement i

Solution

1. Step 1: Check loop start and direction

   Array indices go from 0 to nums.length - 1. Starting at nums.length is out of bounds.

2. Step 2: Correct loop start and decrement

   Loop should start at nums.length - 1 and decrement i to 0 to traverse backward correctly.

3. Final Answer:

   Loop should start at nums.length - 1 and decrement i -> Option D

4. Quick Check:

   Backward loop start = length-1, decrement i [OK]

Hint: Start backward loop at length-1, not length [OK]

Common Mistakes:

• Starting loop at length causing undefined access
• Incrementing index in backward loop
• Wrong loop condition allowing infinite loop

5. Given a doubly linked list, which traversal method allows visiting nodes both forward and backward efficiently?

hard

A. Using next pointers for forward and prev pointers for backward traversal

B. Using only next pointers for both directions

C. Using only prev pointers for both directions

D. Traversing randomly without pointers

Solution

1. Step 1: Understand doubly linked list structure

   Doubly linked lists have two pointers per node: next (forward) and prev (backward).

2. Step 2: Use pointers for traversal

   Forward traversal uses next pointers; backward traversal uses prev pointers efficiently.

3. Final Answer:

   Using next pointers for forward and prev pointers for backward traversal -> Option A

4. Quick Check:

   Doubly linked list uses next and prev pointers [OK]

Hint: Doubly linked list has next and prev pointers [OK]

Common Mistakes:

• Assuming single pointer can traverse both ways
• Ignoring prev pointers in backward traversal
• Thinking traversal can be random