Why Doubly Linked List Over Singly Linked List in DSA Javascript - 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:
null ← [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, find node before 2 (node 1) to delete node 2

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

Why: We need the previous node to change its next pointer to skip node 2

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

1 -> 3 -> null

Why: This removes node 2 from the chain

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

null ← 1 ↔ [curr->2] ↔ 3 → null

Why: We can move backward and forward easily

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

null ← 1 ↔ 3 → null

Why: Both pointers update to remove node 2 cleanly

Result:

Singly Linked List after deletion:
1 -> 3 -> null

Doubly Linked List after deletion:
null ← 1 ↔ 3 → null

Annotated Code

DSA Javascript

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null; // only used in doubly linked list
  }
}

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

  append(value) {
    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) {
    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; // advance to 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 {
  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; // link back
    this.tail = newNode;
  }

  delete(value) {
    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 previous to next
    } else {
      this.head = curr.next; // deleting head
    }

    if (curr.next) {
      curr.next.prev = curr.prev; // link next back to previous
    } else {
      this.tail = curr.prev; // deleting 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);
console.log('Singly Linked List before deletion:');
sList.print();
sList.delete(2);
console.log('Singly Linked List after deletion:');
sList.print();

const dList = new DoublyLinkedList();
dList.append(1);
dList.append(2);
dList.append(3);
console.log('Doubly Linked List before deletion:');
dList.print();
dList.delete(2);
console.log('Doubly Linked List after deletion:');
dList.print();

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

advance curr to node before target to update next pointer

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 }

locate target node directly in doubly linked list

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

update previous node's next pointer or head if deleting first node

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

update next node's prev pointer or tail if deleting last node

Output

Singly Linked List before deletion:

1 -> 2 -> 3 -> null

Singly Linked List after deletion:

1 -> 3 -> null

Doubly Linked List before deletion:

1 ↔ 2 ↔ 3 ↔ null

Doubly Linked List after deletion:

1 ↔ 3 ↔ null

Complexity Analysis

Time: O(n) because we may need to traverse the list to find the node to delete

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

vs Alternative: Doubly linked list allows direct access to previous node, making deletion easier and cleaner compared to singly linked list which requires traversal to find previous node

Edge Cases

Deleting head node

Head pointer updates to next node; prev pointer updates in doubly linked list

DSA Javascript

if (curr.prev) { ... } else { this.head = curr.next; }

Deleting tail node

Tail pointer updates to previous node; next pointer updates in singly linked list

DSA Javascript

if (curr.next) { ... } else { this.tail = curr.prev; }

Deleting node not found

No changes made; function returns early

DSA Javascript

if (!curr) return;

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 links both ways.

Common Mistakes

Mistake: Trying to delete a node in singly linked list without tracking previous node
Fix: Always keep track of the node before the target to update its next pointer

Mistake: Not updating both prev and next pointers in doubly linked list when deleting
Fix: Update both the previous node's next and the next node's prev pointers to maintain list integrity

Summary

It lets you move forward and backward easily, making some operations like deletion simpler.

Use it when you need to traverse in both directions or delete nodes quickly without searching for previous nodes.

The key is that each node knows both its next and previous neighbors, unlike singly linked lists.

Practice

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

easy

A. Because it only stores one pointer per node

B. Because it uses less memory than singly linked list

C. Because it allows traversal in both directions easily

D. Because it is simpler to implement

Solution

1. Step 1: Understand traversal directions

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

2. Step 2: Compare memory and complexity

   Doubly linked lists use more memory because each node stores two pointers, but they enable easier backward traversal.

3. Final Answer:

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

4. Quick Check:

   Traversal directions = Both ways [OK]

Hint: Doubly linked lists have two pointers per node [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 define a node in a doubly linked list in JavaScript?

easy

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

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

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

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

Solution

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

   A doubly linked list node must have both prev and next pointers to link backward and forward.

2. Step 2: Check constructor correctness

   class Node { constructor(value) { this.value = value; this.prev = null; this.next = null; } } correctly initializes prev and next to null along with the value.

3. Final Answer:

   class Node { constructor(value) { this.value = value; this.prev = null; this.next = null; } } -> Option A

4. Quick Check:

   Node has prev and next pointers [OK]

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

Common Mistakes:

• Omitting the prev pointer
• Assigning prev to value instead of null
• Defining only next pointer

3. Consider this code snippet for a doubly linked list traversal backward:

let current = tail;
let result = [];
while (current !== null) {
  result.push(current.value);
  current = current.prev;
}
console.log(result);

What will be the output if the list contains nodes with values 1 -> 2 -> 3 (head to tail)?

medium

A. [3, 2, 1]

B. [1, 2, 3]

C. [null]

D. Error: current.prev is undefined

Solution

1. Step 1: Understand traversal starting point

   The traversal starts at tail, which holds the value 3 in the list 1 -> 2 -> 3.

2. Step 2: Trace backward traversal

   It pushes values 3, then moves to 2, pushes 2, then moves to 1, pushes 1, then stops at null.

3. Final Answer:

   [3, 2, 1] -> Option A

4. Quick Check:

   Backward traversal outputs reversed list [OK]

Hint: Backward traversal prints list in reverse order [OK]

Common Mistakes:

• Assuming output is forward order
• Confusing head and tail starting points
• Expecting error due to null check missing

4. The following code tries to remove the last node from a doubly linked list but causes an error:

function removeLast(tail) {
  if (!tail) return null;
  let prevNode = tail.prev;
  prevNode.next = null;
  return prevNode;
}

What is the error and how to fix it?

medium

A. Error because tail is not updated; fix by returning tail instead

B. Error if tail.prev is null; fix by checking if prevNode exists before setting next

C. No error; code works fine

D. Error because next pointer should be set to tail, fix by assigning tail.next = null

Solution

1. Step 1: Identify error cause

   If the list has only one node, tail.prev is null, so prevNode.next causes an error.

2. Step 2: Fix by adding null check

   Before setting prevNode.next = null, check if prevNode exists to avoid error.

3. Final Answer:

   Error if tail.prev is null; fix by checking if prevNode exists before setting next -> Option B

4. Quick Check:

   Check prevNode before access [OK]

Hint: Check for null before accessing prevNode.next [OK]

Common Mistakes:

• Ignoring single-node list edge case
• Assuming tail always has a prev node
• Not returning updated tail correctly

5. You want to implement a feature that requires frequent backward and forward traversal and quick deletion of nodes from anywhere in the list. Which data structure is best and why?

hard

A. Stack, because it supports LIFO operations

B. Singly linked list, because it uses less memory

C. Array, because it allows random access

D. Doubly linked list, because it supports traversal in both directions and easy deletion

Solution

1. Step 1: Analyze traversal needs

   Frequent backward and forward traversal requires a structure that supports moving in both directions easily.

2. Step 2: Analyze deletion needs

   Quick deletion from anywhere is easier if nodes have pointers to previous nodes, so you can update links without full traversal.

3. Step 3: Compare options

   Singly linked lists lack backward pointers, arrays have costly deletions, stacks only allow LIFO access.

4. Final Answer:

   Doubly linked list, because it supports traversal in both directions and easy deletion -> Option D

5. Quick Check:

   Bidirectional traversal + easy deletion = Doubly linked list [OK]

Hint: Bidirectional traversal needs doubly linked list [OK]

Common Mistakes:

• Choosing singly linked list for backward traversal
• Choosing array ignoring deletion cost
• Confusing stack with linked list