Traversal Forward and Backward in DSA Typescript

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

null ← 1 ↔ 2 ↔ 3 ↔ 4 -> null
↑head

Dry Run Walkthrough

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

Goal: Visit all nodes from head to tail, then from tail back to head, printing their values

Step 1: Start at head node (1) for forward traversal

null ← [1↑] ↔ 2 ↔ 3 ↔ 4 -> null

Why: We begin traversal from the first node

Step 2: Move forward to node 2

null ← 1 ↔ [2↑] ↔ 3 ↔ 4 -> null

Why: Visit next node in forward direction

Step 3: Move forward to node 3

null ← 1 ↔ 2 ↔ [3↑] ↔ 4 -> null

Why: Continue forward traversal

Step 4: Move forward to node 4 (tail)

null ← 1 ↔ 2 ↔ 3 ↔ [4↑] -> null

Why: Reached the last node for forward traversal

Step 5: Start backward traversal from tail node (4)

null ← 1 ↔ 2 ↔ 3 ↔ [4↑] -> null

Why: Begin visiting nodes backward from tail

Step 6: Move backward to node 3

null ← 1 ↔ 2 ↔ [3↑] ↔ 4 -> null

Why: Visit previous node in backward direction

Step 7: Move backward to node 2

null ← 1 ↔ [2↑] ↔ 3 ↔ 4 -> null

Why: Continue backward traversal

Step 8: Move backward to node 1 (head)

null ← [1↑] ↔ 2 ↔ 3 ↔ 4 -> null

Why: Reached the first node for backward traversal

Result:

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

Annotated Code

DSA Typescript

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

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

  append(value: number): void {
    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(): string {
    let curr = this.head;
    let result = '';
    while (curr) {
      result += curr.value + ' -> ';
      curr = curr.next; // advance curr to next node
    }
    result += 'null';
    return result;
  }

  traverseBackward(): string {
    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 = curr.next; // advance curr to next node

advance curr to next node -- keeps moving forward until end

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

move curr to previous node -- keeps moving backward until start

Output

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

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

Complexity Analysis

Time: O(n) because each node is visited once in forward and once in backward traversal

Space: O(1) because traversal uses only a few pointers, no extra space grows with input 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 Typescript

if (!this.head) { this.head = newNode; this.tail = newNode; return; }

Single node list

Forward and backward traversal both print the single node value followed by null

DSA Typescript

if (!this.head) { this.head = newNode; this.tail = newNode; return; }

When to Use This Pattern

When you need to visit elements in both directions efficiently, use a doubly linked list and traverse forward with next pointers and backward with prev pointers.

Common Mistakes

Mistake: Trying to traverse backward in a singly linked list without extra steps
Fix: Use a doubly linked list that stores previous pointers to enable backward traversal

Summary

It visits all nodes in a doubly linked list from start to end and then from end to start.

Use it when you want to read or process data in both forward and backward order efficiently.

The key is that each node has links to both next and previous nodes, allowing movement in both directions.

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