Traversal Forward and Backward in DSA Javascript

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 reading a book: forward traversal is reading pages from the first to the last, backward traversal is flipping pages back from the last to the first.

Head -> 1 -> 2 -> 3 -> 4 -> null
Tail ← 1 ← 2 ← 3 ← 4 ← null
↑
Current at head for forward traversal

Dry Run Walkthrough

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

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

Step 1: Start at head node with value 1 for forward traversal

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

Why: We begin traversal from the first node

Step 2: Visit node 1, move curr to next node 2

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

Why: Move forward to visit next node

Step 3: Visit node 2, move curr to next node 3

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

Why: Continue forward traversal

Step 4: Visit node 3, move curr to next node 4

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

Why: Continue forward traversal

Step 5: Visit node 4, curr next is null, forward traversal ends

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

Why: Reached end of list

Step 6: Start backward traversal from tail node 4

null ← 1 ← 2 ← 3 ← 4 [curr←]

Why: Begin backward traversal from last node

Step 7: Visit node 4, move curr to previous node 3

null ← 1 ← 2 ← [curr←3] ← 4

Why: Move backward to previous node

Step 8: Visit node 3, move curr to previous node 2

null ← 1 ← [curr←2] ← 3 ← 4

Why: Continue backward traversal

Step 9: Visit node 2, move curr to previous node 1

null ← [curr←1] ← 2 ← 3 ← 4

Why: Continue backward traversal

Step 10: Visit node 1, curr previous is null, backward traversal ends

[curr←null] ← 1 ← 2 ← 3 ← 4

Why: Reached start of list

Result:

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

Annotated Code

DSA Javascript

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

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  append(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      return;
    }
    this.tail.next = newNode;
    newNode.prev = this.tail;
    this.tail = newNode;
  }

  traverseForward() {
    let curr = this.head;
    let result = '';
    while (curr) {
      result += curr.value + ' -> ';
      curr = curr.next; // advance curr to next node
    }
    result += 'null';
    return result;
  }

  traverseBackward() {
    let curr = this.tail;
    let result = '';
    while (curr) {
      result += curr.value + ' -> ';
      curr = curr.prev; // move curr to previous node
    }
    result += 'null';
    return result;
  }
}

// Driver code
const list = new DoublyLinkedList();
list.append(1);
list.append(2);
list.append(3);
list.append(4);

console.log('Forward traversal:', list.traverseForward());
console.log('Backward traversal:', list.traverseBackward());

curr = this.head;

start forward traversal at head node

curr = curr.next; // advance curr to next node

move forward to next node until end

curr = this.tail;

start backward traversal at tail node

curr = curr.prev; // move curr to previous node

move backward to previous node until start

Output

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

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

Complexity Analysis

Time: O(n) because we visit each node once in forward or backward traversal

Space: O(1) because we use only a few variables regardless of list size

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

Edge Cases

Empty list

Traversal returns 'null' immediately without errors

DSA Javascript

while (curr) { ... }

Single node list

Traversal visits the single node and ends correctly

DSA Javascript

while (curr) { ... }

When to Use This Pattern

When you need to visit elements in both directions efficiently, use traversal on a doubly linked list because it has pointers to both next and previous nodes.

Common Mistakes

Mistake: Trying to traverse backward on a singly linked list without extra steps
Fix: Use a doubly linked list or store nodes in a stack to simulate backward traversal

Mistake: Not updating current pointer correctly causing infinite loops
Fix: Always move current pointer to next or previous node inside the loop

Summary

Traversal forward and backward visits each node from start to end and end to start in a doubly linked list.

Use it when you want to access list elements in both directions efficiently.

The key insight is that doubly linked lists have two pointers per node allowing easy forward and backward moves.

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