Why Doubly Linked List Over Singly Linked List in DSA Typescript - Why It Was Designed This Way

Overview - Why Doubly Linked List Over Singly Linked List

What is it?

A doubly linked list is a chain of elements where each element knows both its next and previous neighbors. This lets you move forward and backward through the list easily. A singly linked list only knows the next element, so you can only move forward. Doubly linked lists add extra links to make navigation and some operations simpler.

Why it matters

Without doubly linked lists, some tasks like going backward or removing elements from the middle become slow or complicated. They solve the problem of limited navigation and inefficient updates in singly linked lists. This makes programs faster and easier to write when you need flexible movement through data.

Where it fits

You should first understand singly linked lists and basic pointers or references. After doubly linked lists, you can learn about circular linked lists, linked list variations, and more complex data structures like trees and graphs that use similar linking ideas.

Mental Model

Core Idea

A doubly linked list lets you move both forward and backward through elements by storing two links per element, unlike singly linked lists that only go forward.

Think of it like...

Imagine a train where each carriage has a connector to the next carriage and also one to the previous carriage. This lets you walk forward or backward along the train easily. A singly linked list is like a train where you can only move forward because each carriage only connects to the next one.

Head ⇄ Node1 ⇄ Node2 ⇄ Node3 ⇄ Null

Each node has two arrows: one pointing to the next node and one pointing to the previous node.

Build-Up - 7 Steps

1

Foundation

Understanding Singly Linked Lists

Concept: Learn what a singly linked list is and how it connects elements in one direction.

A singly linked list is a chain of nodes where each node has data and a pointer to the next node. The last node points to null, marking the end. You can only move forward from the head to the tail. Example: Node1 -> Node2 -> Node3 -> null Operations like adding at the front or traversing forward are simple.

Result

You can move forward through the list but cannot go backward or easily remove nodes without extra work.

Understanding singly linked lists sets the stage for why adding backward links can solve navigation and update problems.

2

Foundation

Basic Structure of Doubly Linked Lists

Concept: Introduce nodes that have two pointers: one to the next node and one to the previous node.

In a doubly linked list, each node stores: - data - pointer to the next node - pointer to the previous node This allows moving forward and backward. Example: null <- Node1 <-> Node2 <-> Node3 -> null The head's previous pointer and tail's next pointer are null.

Result

You can traverse the list in both directions easily.

Knowing the node structure explains how doubly linked lists enable two-way navigation.

3

Intermediate

Advantages in Navigation and Operations

🤔Before reading on: Do you think removing a middle node is easier in singly or doubly linked lists? Commit to your answer.

Concept: Show how doubly linked lists simplify operations like deletion and backward traversal.

In singly linked lists, to remove a node, you must find the previous node to update its next pointer. This requires extra traversal. In doubly linked lists, each node knows its previous node, so removal is direct: - Update previous node's next pointer - Update next node's previous pointer Backward traversal is also straightforward by following previous pointers.

Result

Operations like deletion and reverse traversal become faster and simpler.

Understanding these operational benefits clarifies why doubly linked lists are preferred when flexible navigation or frequent deletions are needed.

4

Intermediate

Memory and Performance Trade-offs

🤔Before reading on: Does adding backward pointers increase or decrease memory use? Commit to your answer.

Concept: Explain the extra memory cost and slight performance impact of storing two pointers per node.

Each node in a doubly linked list stores an extra pointer compared to singly linked lists. This means: - More memory per node - Slightly more work updating two pointers during insertions and deletions However, the benefits in navigation and operation speed often outweigh these costs.

Result

Doubly linked lists use more memory but offer better flexibility.

Knowing the trade-offs helps decide when doubly linked lists are worth the extra cost.

5

Intermediate

Use Cases Favoring Doubly Linked Lists

Concept: Identify scenarios where doubly linked lists are clearly better than singly linked lists.

Doubly linked lists shine when: - You need to traverse backward (e.g., undo operations) - You frequently delete or insert nodes in the middle - You implement complex data structures like deques or navigation histories Singly linked lists are simpler but less flexible in these cases.

Result

You can pick the right list type based on your needs.

Recognizing use cases guides practical data structure choices.

6

Advanced

Implementing Doubly Linked Lists in TypeScript

🤔Before reading on: Do you think updating both pointers in insert/delete is error-prone? Commit to your answer.

Concept: Show a complete TypeScript implementation highlighting pointer updates.

class Node { data: T; next: Node | null = null; prev: Node | null = null; constructor(data: T) { this.data = data; } } class DoublyLinkedList { head: Node | null = null; tail: Node | null = null; append(data: T) { const newNode = new Node(data); if (!this.head) { this.head = this.tail = newNode; } else { this.tail!.next = newNode; newNode.prev = this.tail; this.tail = newNode; } } remove(node: Node) { if (node.prev) node.prev.next = node.next; else this.head = node.next; if (node.next) node.next.prev = node.prev; else this.tail = node.prev; } } // Usage const list = new DoublyLinkedList(); list.append(1); list.append(2); list.append(3); list.remove(list.head!.next!); // removes node with data 2

Result

The list after removal: 1 <-> 3 <-> null

Seeing the code reveals the careful pointer updates needed and why doubly linked lists require attention to detail.

7

Expert

Surprising Edge Cases and Pitfalls

🤔Before reading on: Can forgetting to update one pointer cause list corruption? Commit to your answer.

Concept: Explore subtle bugs like pointer mismatches and how to avoid them.

If you forget to update either the previous or next pointer during insertions or deletions, the list can become corrupted, causing traversal errors or memory leaks. Example bug: - Removing a node but not updating the next node's prev pointer leaves a dangling backward link. Careful testing and helper methods can prevent these issues. Also, circular doubly linked lists add complexity by connecting tail to head, requiring extra care.

Result

Understanding these pitfalls helps write robust doubly linked list code.

Knowing these edge cases prevents subtle bugs that can crash or corrupt programs.

Under the Hood

Each node stores two memory addresses (pointers): one to the next node and one to the previous node. When traversing, the program follows these pointers to move through memory locations of nodes. Insertions and deletions update these pointers to maintain the chain. The doubly linked structure allows bidirectional traversal by following next or prev pointers.

Why designed this way?

Doubly linked lists were designed to overcome the limitation of singly linked lists that only allow forward traversal. By adding a backward pointer, they enable efficient reverse traversal and easier node removal without needing to traverse from the head. The trade-off is extra memory and pointer management complexity, but the flexibility gained is valuable for many applications.

┌───────┐     ┌───────┐     ┌───────┐
│ null  │←prev│ Node1 │->next│ Node2 │->next ...
└───────┘     └───────┘     └───────┘
               ↑    ↓
             prev  next

Each node points backward and forward, forming a chain that can be walked in both directions.

Myth Busters - 4 Common Misconceptions

Quick: Does a doubly linked list always use twice the memory of a singly linked list? Commit yes or no.

Common Belief: Doubly linked lists always use exactly double the memory of singly linked lists.

Reality: While doubly linked lists store an extra pointer per node, the total memory depends on node data size and system pointer size. The increase is roughly one extra pointer per node, not necessarily double the total memory.

Why it matters: Assuming double memory use may discourage using doubly linked lists even when their benefits outweigh the modest extra cost.

Quick: Can you traverse a singly linked list backward without extra data structures? Commit yes or no.

Common Belief: You can easily traverse a singly linked list backward just like a doubly linked list.

Reality: Singly linked lists do not have backward pointers, so backward traversal requires extra work like reversing the list or using a stack, which is inefficient.

Why it matters: Misunderstanding this leads to inefficient code or incorrect assumptions about singly linked list capabilities.

Quick: Is it always better to use doubly linked lists over singly linked lists? Commit yes or no.

Common Belief: Doubly linked lists are always better than singly linked lists because they offer more features.

Reality: Doubly linked lists have extra memory and pointer update costs. For simple forward-only tasks, singly linked lists are simpler and more efficient.

Why it matters: Choosing doubly linked lists unnecessarily can waste resources and complicate code.

Quick: Does adding backward pointers make insertion and deletion operations simpler? Commit yes or no.

Common Belief: Adding backward pointers always makes insertion and deletion operations simpler and less error-prone.

Reality: While backward pointers simplify some operations, they also require careful updates of two pointers per node, increasing the chance of bugs if not handled properly.

Why it matters: Overconfidence in simplicity can lead to subtle bugs and corrupted lists.

Expert Zone

1

Doubly linked lists can be made circular, connecting tail to head, enabling infinite traversal loops and simplifying some algorithms.

2

In multithreaded environments, doubly linked lists require careful locking or atomic operations to avoid pointer inconsistencies.

3

Memory overhead of doubly linked lists can be mitigated by pointer compression or using XOR linked lists, which store combined pointers but are harder to implement.

When NOT to use

Avoid doubly linked lists when memory is very limited or when only forward traversal is needed. Use singly linked lists or arrays instead. For random access, arrays or balanced trees are better choices.

Production Patterns

Doubly linked lists are used in browser history navigation, undo-redo stacks, and implementing deques (double-ended queues). They also appear in OS kernel data structures for process scheduling and memory management.

Connections

Deque (Double-Ended Queue)

Doubly linked lists are a common underlying structure for deques, allowing efficient insertion and deletion at both ends.

Understanding doubly linked lists helps grasp how deques achieve constant-time operations at both front and back.

Undo-Redo Systems in Software

Doubly linked lists model the history of actions, enabling moving backward and forward through states.

Knowing doubly linked lists clarifies how software tracks and reverses user actions efficiently.

Bidirectional Graph Traversal

Doubly linked lists share the concept of two-way connections similar to edges in bidirectional graphs.

Recognizing this connection aids understanding of graph traversal algorithms that move in both directions.

Common Pitfalls

#1 Forgetting to update the previous pointer when inserting a new node.

Wrong approach:

newNode.next = current.next;
current.next = newNode;
// Missing: newNode.prev = current and current.next.prev = newNode

Correct approach:

newNode.next = current.next;
newNode.prev = current;
if (current.next) current.next.prev = newNode;
current.next = newNode;

Root cause:

Not realizing that both next and prev pointers must be updated to maintain list integrity.

#2 Removing a node without updating the next node's previous pointer.

Wrong approach:

if (node.prev) node.prev.next = node.next;
// Missing: if (node.next) node.next.prev = node.prev;

Correct approach:

if (node.prev) node.prev.next = node.next;
if (node.next) node.next.prev = node.prev;

Root cause:

Assuming only one pointer update is needed when removing nodes.

#3 Assuming doubly linked lists automatically handle edge cases like empty or single-node lists.

Wrong approach:

Removing head or tail nodes without checking if they are null or the only node, causing null pointer errors.

Correct approach:

Check if node.prev or node.next is null before updating pointers to handle head and tail correctly.

Root cause:

Overlooking special cases at the ends of the list.

Key Takeaways

Doubly linked lists store two pointers per node, enabling easy forward and backward traversal.

They simplify operations like deletion and reverse traversal compared to singly linked lists but use more memory.

Careful pointer updates are essential to avoid corrupting the list during insertions and deletions.

Choosing between singly and doubly linked lists depends on the need for bidirectional navigation and operation efficiency.

Doubly linked lists underpin many real-world systems like undo-redo and deques, making them a powerful data structure.

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