Create and Initialize Doubly Linked List in DSA Typescript - Deep Dive

Overview - Create and Initialize Doubly Linked List

What is it?

A doubly linked list is a chain of nodes where each node knows both its previous and next neighbor. Creating and initializing it means making this chain from scratch, starting empty or with some values. This structure lets you move forward and backward easily through the list. It is useful when you want flexible insertion and deletion anywhere in the list.

Why it matters

Without doubly linked lists, managing sequences where you need to go both ways or insert/delete in the middle would be slow or complicated. Arrays or singly linked lists can only move forward easily, making some tasks inefficient. Doubly linked lists solve this by linking nodes in two directions, improving performance and flexibility in many programs like browsers, undo features, and music playlists.

Where it fits

Before this, you should understand basic programming concepts like variables, functions, and simple data structures like arrays or singly linked lists. After learning to create and initialize doubly linked lists, you can explore advanced operations like insertion, deletion, traversal, and applications like LRU caches or complex data navigation.

Mental Model

Core Idea

A doubly linked list is a chain of nodes where each node points to both its previous and next node, allowing easy movement in both directions.

Think of it like...

Imagine a train where each carriage is connected to the one before and after it with two couplings, so you can move forward or backward along the train easily.

Head ⇄ Node1 ⇄ Node2 ⇄ Node3 ⇄ Tail
Each arrow shows a link pointing both ways between nodes.

Build-Up - 7 Steps

1

Foundation

Understanding Node Structure Basics

Concept: Learn what a node is and how it stores data and links to neighbors.

A node in a doubly linked list holds three things: the data (value), a pointer to the previous node, and a pointer to the next node. In TypeScript, we create a class Node with these properties. Initially, when a node is alone, both pointers are null.

Result

A Node class that can hold a value and links to previous and next nodes, ready to be connected.

Understanding the node structure is key because the entire list is built by connecting these nodes through their pointers.

2

Foundation

Creating an Empty Doubly Linked List

Concept: Initialize a doubly linked list with no nodes, setting up head and tail pointers.

A doubly linked list class starts with head and tail pointers set to null, meaning the list is empty. This setup allows us to add nodes later and keep track of the start and end of the list.

Result

An empty list with head = null and tail = null, ready to add nodes.

Starting with an empty list sets a clear base state, making it easier to handle edge cases when adding or removing nodes.

3

Intermediate

Initializing List with One Node

🤔Before reading on: Do you think the head and tail point to the same node or different nodes when the list has one node? Commit to your answer.

Concept: Add the first node to the list and update head and tail to point to it.

When adding the first node, both head and tail should point to this single node because it is both the start and end of the list. The node's previous and next pointers remain null.

Result

List with one node: head and tail both point to this node; node.prev = null; node.next = null.

Knowing that head and tail point to the same node in a single-node list simplifies boundary checks in list operations.

4

Intermediate

Adding Multiple Nodes Sequentially

🤔Before reading on: When adding nodes at the end, do you think the tail moves forward or stays fixed? Commit to your answer.

Concept: Add nodes one by one at the end, updating tail and linking nodes properly.

To add a new node at the end, link the current tail's next pointer to the new node, set the new node's previous pointer to the current tail, then update the tail pointer to the new node. The head remains unchanged.

Result

List with multiple nodes linked forward and backward; tail points to last node; head points to first node.

Updating tail and linking nodes correctly ensures the list remains consistent and traversal works both ways.

5

Intermediate

TypeScript Class for Doubly Linked List

Concept: Combine node and list logic into a reusable TypeScript class with constructor and methods.

Define a DoublyLinkedList class with head and tail properties. Include methods to initialize the list empty or with an array of values. The constructor loops through values, creating nodes and linking them as described. This encapsulates creation and initialization cleanly.

Result

A reusable class that can create empty or pre-filled doubly linked lists easily.

Encapsulating logic in a class makes the list easier to use and maintain in real projects.

6

Advanced

Handling Edge Cases in Initialization

🤔Before reading on: What happens if you initialize with an empty array? Does the list have nodes or remain empty? Commit to your answer.

Concept: Ensure the list handles empty or null inputs gracefully during initialization.

When initializing with an empty array or no input, the list should remain empty with head and tail null. The constructor checks input length and skips node creation if empty. This prevents errors and unexpected states.

Result

Robust list initialization that works with empty or missing input without errors.

Handling edge cases during initialization prevents bugs and makes the data structure reliable in all situations.

7

Expert

Memory and Reference Management in TypeScript

🤔Before reading on: Do you think nodes are copied or referenced when linked in TypeScript? Commit to your answer.

Concept: Understand how TypeScript manages object references for nodes and implications for list behavior.

In TypeScript, nodes are objects referenced by variables. When linking nodes, we assign references, not copies. This means changing one node affects the list structure directly. Properly managing these references avoids memory leaks and dangling pointers.

Result

Efficient memory use with shared references; changes to nodes reflect immediately in the list.

Knowing that nodes are referenced objects helps prevent common bugs like accidental duplication or lost links.

Under the Hood

Each node is an object stored in memory with pointers (references) to previous and next nodes. The list maintains head and tail references to the first and last nodes. Adding or removing nodes updates these pointers to maintain the chain. The runtime manages memory for these objects, and TypeScript's references ensure nodes are linked without copying data.

Why designed this way?

Doubly linked lists were designed to allow efficient two-way traversal and easy insertion/deletion anywhere in the list. Unlike arrays, they don't require shifting elements. The two pointers per node add some memory overhead but provide flexibility. This design balances speed and memory for many real-world applications.

┌───────┐     ┌───────┐     ┌───────┐
│ Head  │────▶│ Node1 │────▶│ Node2 │────▶ null
└──┬────┘     └──┬────┘     └──┬────┘
     ◀───────────│◀───────────│
                 │            │
               null          Tail

Myth Busters - 3 Common Misconceptions

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

Common Belief: A doubly linked list always uses double the memory of a singly linked list because it stores two pointers per node.

Reality: While each node stores two pointers, the overall memory overhead depends on node size and usage. Sometimes the extra pointer is negligible compared to data size, and the benefits outweigh the cost.

Why it matters: Assuming doubly linked lists are always too heavy might prevent using them where they improve performance and code simplicity.

Quick: Can you traverse a doubly linked list backward without extra code? Commit yes or no.

Common Belief: You need special code or extra data structures to move backward in a doubly linked list.

Reality: Each node has a previous pointer, so you can move backward naturally by following these pointers without extra structures.

Why it matters: Misunderstanding traversal can lead to inefficient or complicated code when simple backward traversal is available.

Quick: When initializing a doubly linked list with one node, do head and tail point to different nodes? Commit yes or no.

Common Belief: Head and tail always point to different nodes, even if the list has only one node.

Reality: When the list has one node, head and tail both point to that same node.

Why it matters: Incorrect assumptions about head and tail can cause bugs in list operations like insertion or deletion.

Expert Zone

1

The choice between updating head or tail first during insertion affects edge case handling and can prevent subtle bugs.

2

In TypeScript, careful null checks are needed because pointers can be null, and forgetting this leads to runtime errors.

3

Memory leaks can occur if nodes are not properly disconnected before removal, especially in environments with manual resource management.

When NOT to use

Avoid doubly linked lists when memory is extremely limited or when random access by index is required frequently; arrays or balanced trees may be better alternatives.

Production Patterns

Doubly linked lists are used in browser history navigation, undo-redo stacks, and LRU cache implementations where quick two-way traversal and efficient insertions/deletions are critical.

Connections

Singly Linked List

Builds-on

Understanding singly linked lists helps grasp the added backward link in doubly linked lists, showing how extra pointers enable two-way traversal.

Cache Eviction Algorithms

Application

Doubly linked lists are fundamental in implementing LRU caches, where quick removal and insertion of nodes represent cache hits and evictions.

Train Carriage Couplings (Mechanical Engineering)

Structural similarity

The way train carriages connect front and back mirrors how nodes link in a doubly linked list, illustrating the importance of two-way connections for flexible movement.

Common Pitfalls

#1 Forgetting to update the previous pointer when adding a new node at the end.

Wrong approach:

tail.next = newNode;
// missing newNode.prev = tail;
tail = newNode;

Correct approach:

tail.next = newNode;
newNode.prev = tail;
tail = newNode;

Root cause:

Not realizing that both forward and backward links must be updated to maintain list integrity.

#2 Setting head or tail to null incorrectly when list still has nodes.

Wrong approach:

head = null;
// but nodes still exist and tail is not updated

Correct approach:

head = null;
tail = null;
// only when list is truly empty

Root cause:

Confusing empty list state with partial list, leading to broken references.

#3 Initializing list with an array but not linking nodes properly.

Wrong approach:

for (let value of values) {
let node = new Node(value);
tail = node; // tail updated but no links set
}

Correct approach:

for (let value of values) {
let node = new Node(value);
if (!head) {
head = node;
tail = node;
} else {
tail.next = node;
node.prev = tail;
tail = node;
}
}

Root cause:

Missing the step to connect nodes bidirectionally during initialization.

Key Takeaways

A doubly linked list consists of nodes linked both forward and backward, enabling easy two-way traversal.

Creating and initializing the list involves setting up head and tail pointers and linking nodes correctly.

Handling edge cases like empty lists or single-node lists is crucial for robust implementation.

In TypeScript, nodes are referenced objects, so pointer updates directly affect the list structure.

Understanding these basics prepares you for advanced operations and real-world applications like caches and navigation.

Practice

1. What is the main difference between a doubly linked list and a singly linked list?

easy

A. A doubly linked list stores data in arrays instead of nodes.

B. A doubly linked list does not use pointers at all.

C. A doubly linked list can only be traversed forward.

D. A doubly linked list has nodes with pointers to both previous and next nodes.

Solution

1. Step 1: Understand node structure in doubly linked list

   Each node in a doubly linked list contains data and two pointers: one to the previous node and one to the next node.

2. Step 2: Compare with singly linked list

   A singly linked list node has only one pointer to the next node, so it can only be traversed forward.

3. Final Answer:

   A doubly linked list has nodes with pointers to both previous and next nodes. -> Option D

4. Quick Check:

   Doubly linked list = two pointers per node [OK]

Hint: Remember: doubly means two pointers per node [OK]

Common Mistakes:

• Thinking doubly linked list uses arrays
• Assuming it can only go forward
• Confusing pointer usage

2. Which of the following TypeScript code snippets correctly defines a node class for a doubly linked list?

easy

A. class Node { data: number; next: Node; constructor(data: number) { this.data = data; this.next = null; } }

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

C. class Node { data: number; prev: Node; constructor(data: number) { this.data = data; this.prev = null; } }

D. class Node { data: number; next: number; prev: number; constructor(data: number) { this.data = data; this.next = 0; this.prev = 0; } }

Solution

1. Step 1: Check for both next and prev pointers

   class Node { data: number; next: Node | null; prev: Node | null; constructor(data: number) { this.data = data; this.next = null; this.prev = null; } } defines both next and prev as Node or null, which is correct for doubly linked list nodes.

2. Step 2: Verify constructor initialization

   class Node { data: number; next: Node | null; prev: Node | null; constructor(data: number) { this.data = data; this.next = null; this.prev = null; } } initializes next and prev to null, which is proper for a new node.

3. Final Answer:

   class Node { data: number; next: Node | null; prev: Node | null; constructor(data: number) { this.data = data; this.next = null; this.prev = null; } } -> Option B

4. Quick Check:

   Node class needs next and prev pointers [OK]

Hint: Look for both next and prev properties initialized to null [OK]

Common Mistakes:

• Missing prev pointer in node class
• Using wrong types for pointers
• Initializing pointers with numbers instead of null

3. What will be the output of the following TypeScript code that creates a doubly linked list with nodes 10, 20, 30 and prints the list forward?

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

class DoublyLinkedList {
  head: Node | null = null;

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

  printForward() {
    let current = this.head;
    let result = '';
    while (current) {
      result += current.data + ' -> ';
      current = current.next;
    }
    result += 'null';
    console.log(result);
  }
}

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

medium

A. 10 -> 20 -> 30 -> null

B. 30 -> 20 -> 10 -> null

C. null -> 10 -> 20 -> 30

D. 10 -> 20 -> null

Solution

1. Step 1: Append nodes 10, 20, 30 in order

   Nodes are added at the end, so list order is 10, then 20, then 30.

2. Step 2: Print list forward

   printForward traverses from head to next nodes, printing data with arrows, ending with null.

3. Final Answer:

   10 -> 20 -> 30 -> null -> Option A

4. Quick Check:

   Appending adds to tail, printForward shows 10 to 30 [OK]

Hint: Appending adds nodes at tail; printForward shows head to tail [OK]

Common Mistakes:

• Confusing print order as reversed
• Missing last node in output
• Printing null at start instead of end

4. Identify the error in the following TypeScript code that tries to append a node to a doubly linked list:

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

class DoublyLinkedList {
  head: Node | null = null;

  append(data: number) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = newNode;
    // Missing line here
  }
}

medium

A. The code misses setting newNode.prev to current before appending.

B. The code should set head to newNode even if head exists.

C. The constructor should initialize next and prev to undefined, not null.

D. The while loop should check current.prev instead of current.next.

Solution

1. Step 1: Check append logic for doubly linked list

   When appending, newNode.prev must point to current (the last node) to maintain backward link.

2. Step 2: Identify missing pointer assignment

   The code sets current.next = newNode but does not set newNode.prev = current, breaking backward link.

3. Final Answer:

   The code misses setting newNode.prev to current before appending. -> Option A

4. Quick Check:

   newNode.prev must link to previous node [OK]

Hint: Always set newNode.prev = last node when appending [OK]

Common Mistakes:

• Forgetting to set newNode.prev
• Changing head incorrectly
• Checking wrong pointer in loop

5. You want to create a doubly linked list from an array of numbers [5, 15, 25] and then reverse the list by changing pointers (not data). Which sequence of pointer changes correctly reverses the list?

hard

A. For each node, set next to prev and leave prev unchanged; head remains same.

B. For each node, set next to null and prev to null; then append nodes in reverse order.

C. For each node, swap its next and prev pointers; then update head to last node.

D. For each node, swap data values instead of pointers; head stays unchanged.

Solution

1. Step 1: Understand reversing a doubly linked list by pointers

   Reversing means for each node, next and prev pointers must be swapped to reverse direction.

2. Step 2: Update head pointer

   After swapping pointers, head must point to the original tail (last node) to reflect new start.

3. Final Answer:

   For each node, swap its next and prev pointers; then update head to last node. -> Option C

4. Quick Check:

   Swap next and prev, then reset head [OK]

Hint: Swap next and prev pointers on all nodes, then reset head [OK]

Common Mistakes:

• Only swapping data, not pointers
• Not updating head after reversal
• Setting pointers to null incorrectly