Doubly Linked List Structure and Node Design in DSA Typescript - Deep Dive

Overview - Doubly Linked List Structure and Node Design

What is it?

A doubly linked list is a chain of nodes where each node knows about the node before it and the node after it. Each node holds some data and two links: one to the previous node and one to the next node. This structure allows moving forward and backward through the list easily. It is useful when you need flexible insertion and deletion from both ends or the middle.

Why it matters

Without doubly linked lists, moving backward through a list would be slow or impossible without extra work. They solve the problem of efficient two-way navigation and easy updates in a list. This makes programs faster and simpler when managing sequences of items that change often, like undo features or browser history.

Where it fits

Before learning doubly linked lists, you should understand basic linked lists and nodes. After this, you can learn about more complex structures like circular doubly linked lists, linked list algorithms, or trees that use similar node designs.

Mental Model

Core Idea

A doubly linked list is a chain of nodes where each node points both to the next and the previous node, enabling easy two-way navigation and updates.

Think of it like...

Imagine a train where each carriage has a connector to the carriage in front and the one behind, so you can move forward or backward along the train easily.

Head ⇄ Node ⇄ Node ⇄ Node ⇄ Tail
Each node: [Prev | Data | Next]
Prev points to previous node or null
Next points to next node or null

Build-Up - 7 Steps

1

Foundation

Understanding a Single Node Structure

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

A node in a doubly linked list holds three parts: the data, a pointer to the previous node, and a pointer to the next node. In TypeScript, it looks like this: class Node { data: T; prev: Node | null; next: Node | null; constructor(data: T) { this.data = data; this.prev = null; this.next = null; } } This means each node can connect backward and forward.

Result

You have a blueprint for a node that can hold data and connect to neighbors on both sides.

Understanding the node's dual links is key because it enables two-way movement and flexible list changes.

2

Foundation

Basic Doubly Linked List Setup

Concept: How nodes connect to form the full doubly linked list structure.

A doubly linked list keeps track of the first node (head) and the last node (tail). When you add nodes, you link the new node's prev to the current tail and the tail's next to the new node. If the list is empty, head and tail both point to the new node. class DoublyLinkedList { head: Node | null = null; tail: Node | null = null; append(data: T) { const newNode = new Node(data); if (!this.tail) { this.head = newNode; this.tail = newNode; } else { newNode.prev = this.tail; this.tail.next = newNode; this.tail = newNode; } } } This creates a chain where each node knows its neighbors.

Result

A list where nodes are linked forward and backward, with clear start and end points.

Knowing how head and tail pointers work helps manage the list ends efficiently.

3

Intermediate

Navigating Forward and Backward

🤔Before reading on: Do you think you can move backward through the list as easily as forward? Commit to yes or no.

Concept: Using the prev and next pointers to move through the list in both directions.

To move forward, start at head and follow next pointers until null. To move backward, start at tail and follow prev pointers until null. Example: let current = list.head; while (current) { console.log(current.data); current = current.next; } let currentBack = list.tail; while (currentBack) { console.log(currentBack.data); currentBack = currentBack.prev; } This shows how the doubly linked list supports two-way traversal.

Result

You can print or access all nodes from start to end and from end to start.

Understanding two-way traversal is crucial for algorithms that need backward steps, like undo or reverse iteration.

4

Intermediate

Inserting Nodes in the Middle

🤔Before reading on: When inserting a node in the middle, do you think you need to update one or two neighboring nodes? Commit to your answer.

Concept: How to insert a new node between two existing nodes by updating four pointers.

To insert a node between nodeA and nodeB: 1. Set newNode.prev = nodeA 2. Set newNode.next = nodeB 3. Set nodeA.next = newNode 4. Set nodeB.prev = newNode Example: function insertAfter(nodeA: Node, data: T) { const newNode = new Node(data); const nodeB = nodeA.next; newNode.prev = nodeA; newNode.next = nodeB; nodeA.next = newNode; if (nodeB) { nodeB.prev = newNode; } } This keeps the list connected correctly.

Result

The new node is linked properly between two nodes, preserving the chain.

Knowing to update both neighbors' pointers prevents broken links and list corruption.

5

Intermediate

Removing Nodes Safely

🤔Before reading on: When removing a node, do you think you only need to update the previous node's next pointer? Commit to yes or no.

Concept: Removing a node requires updating both previous and next nodes to skip the removed node.

To remove a node: 1. If node.prev exists, set node.prev.next = node.next 2. If node.next exists, set node.next.prev = node.prev 3. If node is head, update head to node.next 4. If node is tail, update tail to node.prev Example: 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; } } This safely removes the node without breaking the list.

Result

The node is removed and the list remains fully connected.

Updating both neighbors and head/tail pointers avoids dangling references and keeps list integrity.

6

Advanced

TypeScript Node Design with Generics

🤔Before reading on: Do you think using generics in node design limits the data types you can store? Commit to yes or no.

Concept: Using TypeScript generics to make nodes flexible for any data type while keeping type safety.

Generics allow the node to hold any type of data while ensuring type correctness. class Node { data: T; prev: Node | null; next: Node | null; constructor(data: T) { this.data = data; this.prev = null; this.next = null; } } This means you can create a list of numbers, strings, or custom objects without rewriting the node class.

Result

A reusable node design that works with any data type safely.

Using generics increases code reuse and prevents type errors in complex applications.

7

Expert

Memory and Performance Considerations

🤔Before reading on: Do you think doubly linked lists use more memory than singly linked lists? Commit to yes or no.

Concept: Doubly linked lists use extra memory for two pointers per node but offer faster two-way traversal and easier updates.

Each node stores two pointers (prev and next), doubling pointer memory compared to singly linked lists. This extra memory cost is the tradeoff for: - O(1) insertion and deletion from both ends and middle - Easy backward traversal In performance-critical systems, this tradeoff matters. Sometimes arrays or singly linked lists are better if memory is tight or backward traversal is not needed.

Result

Understanding the memory cost helps choose the right data structure for the task.

Knowing the tradeoff between memory and flexibility guides better design decisions in real systems.

Under the Hood

Internally, each node is an object with three fields: data, prev pointer, and next pointer. The list maintains references to head and tail nodes. When nodes are linked, their pointers reference other node objects in memory. This creates a doubly connected chain. Operations like insertion or removal update these pointers to maintain the chain without copying or moving data. The garbage collector frees removed nodes when no references remain.

Why designed this way?

Doubly linked lists were designed to solve the problem of efficient two-way navigation and quick updates in dynamic sequences. Early computer memory was limited, so storing only two pointers per node was a good balance between flexibility and memory use. Alternatives like arrays require shifting elements on insertion or deletion, which is slower. Singly linked lists only allow one-way traversal, limiting use cases.

┌───────┐     ┌───────┐     ┌───────┐
│ Node1 │ ⇄ │ Node2 │ ⇄ │ Node3 │
└───────┘     └───────┘     └───────┘
  ↑  ↓         ↑  ↓         ↑  ↓
 null prev   prev/next   next null

Head points to Node1
Tail points to Node3

Myth Busters - 4 Common Misconceptions

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

Common Belief: Doubly linked lists always use exactly twice the memory of singly linked lists because they have two pointers per node.

Reality: While doubly linked lists have two pointers per node, the actual memory overhead depends on the system and node data size. Sometimes the extra pointer is small compared to data size, so the relative overhead is less than double.

Why it matters: Assuming exact double memory use can lead to rejecting doubly linked lists unnecessarily when their benefits outweigh the small extra cost.

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

Common Belief: You need extra memory or a stack to move backward through a doubly linked list.

Reality: Doubly linked lists store a direct pointer to the previous node, so you can move backward easily without extra memory.

Why it matters: Misunderstanding this leads to inefficient code that wastes memory or time.

Quick: When removing a node, is it enough to update only one neighbor's pointer? Commit to yes or no.

Common Belief: Updating only the previous node's next pointer is enough to remove a node safely.

Reality: You must update both the previous node's next pointer and the next node's prev pointer to keep the list intact.

Why it matters: Failing to update both pointers breaks the list, causing bugs and crashes.

Quick: Does using generics in TypeScript limit the types you can store in nodes? Commit to yes or no.

Common Belief: Generics restrict the node to only one data type and reduce flexibility.

Reality: Generics allow nodes to store any data type while keeping type safety and flexibility.

Why it matters: Misunderstanding generics can cause developers to write less reusable or unsafe code.

Expert Zone

1

The choice of null versus sentinel nodes affects edge case handling and code simplicity.

2

Pointer updates must be done carefully in multi-threaded environments to avoid race conditions.

3

Memory locality in doubly linked lists is poor compared to arrays, affecting cache performance.

When NOT to use

Avoid doubly linked lists when memory is very limited or when you only need one-way traversal. Use arrays for fast random access or singly linked lists for simpler one-way sequences.

Production Patterns

Doubly linked lists are used in undo/redo stacks, browser history, and music playlists where two-way navigation and frequent insertions/deletions happen. They also appear in complex data structures like LRU caches and some graph algorithms.

Connections

Singly Linked List

Doubly linked lists build on singly linked lists by adding backward links.

Understanding singly linked lists helps grasp the added complexity and benefits of doubly linked lists.

Cache Memory in Computer Architecture

Doubly linked lists have poor memory locality compared to arrays, affecting cache performance.

Knowing how memory access patterns affect speed helps choose data structures that perform well on modern hardware.

Undo/Redo Functionality in Software Design

Doubly linked lists model the two-way navigation needed for undo and redo operations.

Recognizing this connection clarifies why doubly linked lists are ideal for managing reversible actions.

Common Pitfalls

#1 Forgetting to update the prev pointer of the next node when inserting a new node.

Wrong approach:

newNode.prev = nodeA;
newNode.next = nodeB;
nodeA.next = newNode;
// Missing: nodeB.prev = newNode;

Correct approach:

newNode.prev = nodeA;
newNode.next = nodeB;
nodeA.next = newNode;
if (nodeB) {
nodeB.prev = newNode;
}

Root cause:

Not realizing both neighbors must update their pointers to maintain the chain.

#2 Removing a node by only updating the previous node's next pointer, leaving the next node's prev pointer unchanged.

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 one pointer update is enough to remove a node safely.

#3 Setting head or tail incorrectly when inserting or removing nodes at the ends.

Wrong approach:

When removing head:
this.head = this.head.next; // but not updating new head.prev = null;

Correct approach:

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

Root cause:

Overlooking special cases at list boundaries causes broken links.

Key Takeaways

A doubly linked list node stores data and two pointers: one to the previous node and one to the next node.

This structure allows easy two-way traversal and efficient insertion or removal anywhere in the list.

Properly updating both neighbors' pointers is essential to keep the list connected and avoid bugs.

Using generics in TypeScript makes the node design flexible and type-safe for any data type.

Doubly linked lists trade extra memory for powerful navigation and update capabilities, making them ideal for many real-world applications.

Practice

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

easy

A. A doubly linked list node has pointers to both the previous and next nodes.

B. A doubly linked list node stores data in a different format.

C. A doubly linked list node can only point to the next node.

D. A doubly linked list node does not store any data.

Solution

1. Step 1: Understand node pointers in singly linked list

   A singly linked list node has only one pointer to the next node.

2. Step 2: Understand node pointers in doubly linked list

   A doubly linked list node has two pointers: one to the previous node and one to the next node.

3. Final Answer:

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

4. Quick Check:

   Doubly linked list nodes have two pointers [OK]

Hint: Remember: doubly linked means two directions [OK]

Common Mistakes:

• Thinking doubly linked nodes only point forward
• Confusing data storage with pointer structure
• Assuming doubly linked nodes do not store data

2. Which of the following is the correct TypeScript syntax to define a doubly linked list node class with data of type number?

easy

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

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

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

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

Solution

1. Step 1: Check property types for next and prev

   Since next and prev can be null initially, their types must allow null (Node | null).

2. Step 2: Verify constructor initializes all properties

   The constructor sets data and initializes next and prev to null correctly.

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 A

4. Quick Check:

   Allow null for next and prev in TypeScript [OK]

Hint: Use 'Node | null' for nullable pointers [OK]

Common Mistakes:

• Not allowing next and prev to be null
• Forgetting to initialize next and prev in constructor
• Setting next and prev types incorrectly

3. What will be the output of the following TypeScript code snippet?

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

const node1 = new Node(10);
const node2 = new Node(20);
node1.next = node2;
node2.prev = node1;

console.log(node1.next?.data);
console.log(node2.prev?.data);

medium

A. Error at runtime

B. 10\n20

C. undefined\nundefined

D. 20\n10

Solution

1. Step 1: Trace node1.next and node2.prev assignments

   node1.next points to node2, so node1.next.data is 20. node2.prev points to node1, so node2.prev.data is 10.

2. Step 2: Check console.log outputs

   console.log(node1.next?.data) prints 20, console.log(node2.prev?.data) prints 10.

3. Final Answer:

   20 10 -> Option D

4. Quick Check:

   next and prev pointers give 20 and 10 respectively [OK]

Hint: Follow next and prev pointers to get data [OK]

Common Mistakes:

• Confusing which node data is printed
• Ignoring optional chaining and assuming errors
• Mixing up prev and next pointers

4. Identify the error in the following TypeScript code for a doubly linked list node and select the fix.

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

medium

A. Change data type from number to any.

B. Remove the constructor to fix the error.

C. Change next and prev types to 'Node | null' to allow null assignment.

D. Initialize next and prev with new Node() instead of null.

Solution

1. Step 1: Analyze type declarations and assignments

   next and prev are typed as Node but assigned null, which is invalid in TypeScript.

2. Step 2: Fix type to allow null

   Changing next and prev types to 'Node | null' allows null assignment and fixes the error.

3. Final Answer:

   Change next and prev types to 'Node | null' to allow null assignment. -> Option C

4. Quick Check:

   Nullable pointers need 'Node | null' type [OK]

Hint: Allow null in pointer types to avoid errors [OK]

Common Mistakes:

• Leaving next and prev as non-nullable types
• Trying to assign new Node() without data
• Removing constructor unnecessarily

5. You want to insert a new node with data 30 between two existing nodes in a doubly linked list: nodeA and nodeB, where nodeA.next = nodeB and nodeB.prev = nodeA. Which sequence of pointer updates correctly inserts the new node?

hard

A. nodeA.next = newNode; nodeB.prev = newNode; newNode.next = nodeB; newNode.prev = nodeA;

B. newNode.prev = nodeA; newNode.next = nodeB; nodeA.next = newNode; nodeB.prev = newNode;

C. newNode.next = nodeA; newNode.prev = nodeB; nodeA.prev = newNode; nodeB.next = newNode;

D. nodeA.prev = newNode; nodeB.next = newNode; newNode.prev = nodeB; newNode.next = nodeA;

Solution

1. Step 1: Set newNode pointers to link between nodeA and nodeB

   newNode.prev must point to nodeA and newNode.next must point to nodeB to fit between them.

2. Step 2: Update nodeA and nodeB pointers to include newNode

   nodeA.next should point to newNode and nodeB.prev should point to newNode to complete the insertion.

3. Final Answer:

   newNode.prev = nodeA; newNode.next = nodeB; nodeA.next = newNode; nodeB.prev = newNode; -> Option B

4. Quick Check:

   Link newNode between nodeA and nodeB correctly [OK]

Hint: Link newNode pointers first, then update neighbors [OK]

Common Mistakes:

• Mixing up prev and next pointers
• Updating neighbors before setting newNode pointers
• Reversing nodeA and nodeB in assignments