Why Doubly Linked List Over Singly Linked List in DSA Typescript - Why This Pattern

Mental Model

A doubly linked list lets you move forward and backward easily, unlike a singly linked list which only moves forward.

Analogy: Think of a train with cars connected front and back. You can walk from the first car to the last or go back from the last to the first. A singly linked list is like a train where you can only walk forward.

Singly Linked List:
head -> [1] -> [2] -> [3] -> null

Doubly Linked List:
head ↔ [1] ↔ [2] ↔ [3] ↔ null

Dry Run Walkthrough

Input: list: 1->2->3, delete node 2

Goal: Show how deleting a middle node is easier in doubly linked list than singly linked list

Step 1: In singly linked list, start at head to find node before 2

head -> [1] -> [2] -> [3] -> null

Why: We need the node before 2 to remove 2 by changing its next pointer

Step 2: Change node 1's next pointer to node 3, skipping node 2

head -> [1] -> [3] -> null

Why: This removes node 2 from the chain

Step 3: In doubly linked list, directly access node 2 and update pointers

head ↔ [1] ↔ [2] ↔ [3] ↔ null

Why: We can remove node 2 without traversing from head

Step 4: Set node 1's next to node 3 and node 3's prev to node 1

head ↔ [1] ↔ [3] ↔ null

Why: Pointers in both directions update to remove node 2 cleanly

Result:

Singly Linked List after deletion:
head -> [1] -> [3] -> null

Doubly Linked List after deletion:
head ↔ [1] ↔ [3] ↔ 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 SinglyLinkedList {
  head: Node | null;
  constructor() {
    this.head = null;
  }

  append(value: number) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    let curr = this.head;
    while (curr.next) {
      curr = curr.next;
    }
    curr.next = newNode;
  }

  delete(value: number) {
    if (!this.head) return;
    if (this.head.value === value) {
      this.head = this.head.next; // remove head
      return;
    }
    let curr = this.head;
    while (curr.next && curr.next.value !== value) {
      curr = curr.next; // find node before target
    }
    if (curr.next && curr.next.value === value) {
      curr.next = curr.next.next; // skip target node
    }
  }

  print() {
    let curr = this.head;
    let result = '';
    while (curr) {
      result += curr.value + ' -> ';
      curr = curr.next;
    }
    result += 'null';
    console.log(result);
  }
}

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

  append(value: number) {
    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;
  }

  delete(value: number) {
    let curr = this.head;
    while (curr && curr.value !== value) {
      curr = curr.next; // find target node
    }
    if (!curr) return; // not found

    if (curr.prev) {
      curr.prev.next = curr.next; // link prev to next
    } else {
      this.head = curr.next; // removing head
    }

    if (curr.next) {
      curr.next.prev = curr.prev; // link next to prev
    } else {
      this.tail = curr.prev; // removing tail
    }
  }

  print() {
    let curr = this.head;
    let result = '';
    while (curr) {
      result += curr.value + ' <-> ';
      curr = curr.next;
    }
    result += 'null';
    console.log(result);
  }
}

// Driver code
const sList = new SinglyLinkedList();
sList.append(1);
sList.append(2);
sList.append(3);
sList.delete(2);
sList.print();

const dList = new DoublyLinkedList();
dList.append(1);
dList.append(2);
dList.append(3);
dList.delete(2);
dList.print();

while (curr.next && curr.next.value !== value) { curr = curr.next; // find node before target }

Traverse singly linked list to find node before the one to delete

curr.next = curr.next.next; // skip target node

Remove target node by skipping it in next pointer

while (curr && curr.value !== value) { curr = curr.next; // find target node }

Traverse doubly linked list to find target node directly

if (curr.prev) { curr.prev.next = curr.next; // link prev to next } else { this.head = curr.next; // removing head }

Update previous node's next pointer or head if removing first node

if (curr.next) { curr.next.prev = curr.prev; // link next to prev } else { this.tail = curr.prev; // removing tail }

Update next node's prev pointer or tail if removing last node

Output

1 -> 3 -> null

1 <-> 3 <-> null

Complexity Analysis

Time: O(n) because in both lists we may need to traverse nodes to find the one to delete

Space: O(1) because we only use a few pointers and no extra data structures

vs Alternative: Doubly linked list allows backward traversal and easier deletion without needing to find the previous node, saving time in some operations compared to singly linked list

Edge Cases

Deleting head node

Head pointer updates correctly in both lists

DSA Typescript

if (this.head.value === value) {
  this.head = this.head.next; // remove head
  return;
}

Deleting tail node in doubly linked list

Tail pointer updates to previous node

DSA Typescript

if (curr.next) {
  curr.next.prev = curr.prev; // link next to prev
} else {
  this.tail = curr.prev; // removing tail
}

Deleting node not found

No changes made, function returns safely

DSA Typescript

if (!curr) return; // not found

When to Use This Pattern

When a problem needs easy backward traversal or quick deletion of nodes without searching for previous nodes, reach for doubly linked list because it stores pointers both ways.

Common Mistakes

Mistake: In singly linked list deletion, forgetting to find the node before the target node
Fix: Always traverse to the node before the one to delete to update its next pointer

Mistake: In doubly linked list deletion, not updating both prev and next pointers
Fix: Update both prev.next and next.prev pointers to maintain list integrity

Summary

Doubly linked list stores pointers to both next and previous nodes allowing two-way traversal.

Use doubly linked list when you need to move backward or delete nodes efficiently without extra traversal.

The key insight is that having backward pointers removes the need to find previous nodes, simplifying operations.

Practice

1. Why might you choose a doubly linked list over a singly linked list in a program?

easy

A. Because it uses less memory per node

B. Because it allows traversal in both directions easily

C. Because it is simpler to implement

D. Because it only stores one pointer per node

Solution

1. Step 1: Understand traversal capabilities

   A singly linked list allows moving forward only, while a doubly linked list allows moving forward and backward.

2. Step 2: Compare memory and complexity

   Doubly linked lists use more memory and are more complex but provide two-way traversal.

3. Final Answer:

   Because it allows traversal in both directions easily -> Option B

4. Quick Check:

   Two-way traversal = A [OK]

Hint: Doubly means two directions, singly means one [OK]

Common Mistakes:

• Thinking doubly linked lists use less memory
• Confusing simplicity with singly linked lists
• Assuming singly linked lists allow backward traversal

2. Which of the following is the correct way to declare a node in a doubly linked list in TypeScript?

easy

A. class Node { value: number; next: Node; }

B. class Node { value: number; prev: Node; }

C. class Node { value: number; next: Node | null; prev: Node | null; }

D. class Node { value: number; next: Node | null; }

Solution

1. Step 1: Identify required pointers for doubly linked list node

   A doubly linked list node must have both next and prev pointers, which can be null if no neighbor exists.

2. Step 2: Check TypeScript syntax for nullable pointers

   Using Node | null correctly allows for the end nodes to have null pointers.

3. Final Answer:

   class Node { value: number; next: Node | null; prev: Node | null; } -> Option C

4. Quick Check:

   Doubly linked node needs next and prev with nulls [OK]

Hint: Doubly linked nodes have next and prev pointers [OK]

Common Mistakes:

• Omitting the prev pointer
• Not allowing null for next or prev
• Using only one pointer like singly linked list

3. Consider this TypeScript code snippet for a doubly linked list node insertion at the front:

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

class DoublyLinkedList {
  head: Node | null = null;
  insertFront(value: number) {
    const newNode = new Node(value);
    if (this.head) {
      newNode.next = this.head;
      this.head.prev = newNode;
    }
    this.head = newNode;
  }
}

const list = new DoublyLinkedList();
list.insertFront(10);
list.insertFront(20);
list.insertFront(30);

let current = list.head;
const result = [];
while (current) {
  result.push(current.value);
  current = current.next;
}
console.log(result);

What will be printed?

medium

A. [10, 30, 20]

B. [10, 20, 30]

C. [20, 30, 10]

D. [30, 20, 10]

Solution

1. Step 1: Trace insertFront calls

   First insert 10: list is 10. Then insert 20 at front: list is 20 -> 10. Then insert 30 at front: list is 30 -> 20 -> 10.

2. Step 2: Traverse from head to next

   Starting at head (30), next is 20, then 10, then null. So collected values are [30, 20, 10].

3. Final Answer:

   [30, 20, 10] -> Option D

4. Quick Check:

   Insert front reverses order = [30, 20, 10] [OK]

Hint: Insert front adds new node before head [OK]

Common Mistakes:

• Assuming insertion appends at end
• Mixing order of traversal
• Ignoring prev pointer effects

4. This TypeScript code tries to delete the last node from a doubly linked list but has a bug:

deleteLast() {
  if (!this.head) return;
  let current = this.head;
  while (current.next) {
    current = current.next;
  }
  current.prev.next = null;
}

What is the bug here?

medium

A. It does not handle the case when list has only one node

B. It incorrectly sets current.next to null instead of current.prev.next

C. It causes infinite loop in the while

D. It deletes the head node instead of the last node

Solution

1. Step 1: Analyze deletion logic

   The code moves to the last node by following next pointers. Then it sets current.prev.next = null to remove last node.

2. Step 2: Check edge case for single node list

   If list has only one node, current.prev is null, so current.prev.next causes error.

3. Final Answer:

   It does not handle the case when list has only one node -> Option A

4. Quick Check:

   Single node list needs special case [OK]

Hint: Check for single node before accessing prev [OK]

Common Mistakes:

• Ignoring single node edge case
• Assuming prev is always non-null
• Confusing next and prev pointers

5. You want to implement a feature that requires frequent backward traversal from any node in a list. Which data structure is best and why? Options: A) Singly linked list because it uses less memory B) Circular singly linked list because it loops infinitely C) Array because it supports random access D) Doubly linked list because it allows backward traversal efficiently

hard

A. Doubly linked list because it allows backward traversal efficiently

B. Circular singly linked list because it loops infinitely

C. Array because it supports random access

D. Singly linked list because it uses less memory

Solution

1. Step 1: Understand backward traversal need

   Backward traversal means moving from a node to its previous nodes efficiently.

2. Step 2: Compare data structures for backward traversal

   Singly linked lists do not have backward pointers. Arrays allow random access but not linked traversal. Circular singly linked lists loop but do not support backward traversal. Doubly linked lists have prev pointers for efficient backward moves.

3. Final Answer:

   Doubly linked list because it allows backward traversal efficiently -> Option A

4. Quick Check:

   Backward traversal needs prev pointers [OK]

Hint: Backward moves need prev pointers, only doubly linked lists have them [OK]

Common Mistakes:

• Choosing singly linked list for backward traversal
• Confusing arrays with linked lists
• Thinking circular singly linked lists support backward moves