Insert at Beginning of Doubly Linked List in DSA Typescript - Deep Dive

Overview - Insert at Beginning of Doubly Linked List

What is it?

A doubly linked list is a chain of nodes where each node points to both its previous and next nodes. Inserting at the beginning means adding a new node before the current first node. This operation updates pointers so the new node becomes the first in the list. It helps quickly add items to the front without shifting others.

Why it matters

Without this operation, adding items at the start would be slow or complicated, especially for large lists. It allows efficient updates at the front, which is common in many real-world tasks like undo history or recent items. Without it, programs would waste time moving data or lose the ability to quickly access new entries.

Where it fits

Before learning this, you should understand what a linked list is and how nodes connect. After this, you can learn about inserting at the end, deleting nodes, or traversing the list. This is a foundational step in mastering linked list manipulations.

Mental Model

Core Idea

Inserting at the beginning of a doubly linked list means creating a new node and adjusting pointers so it becomes the new head, linking forward to the old head and backward to null.

Think of it like...

Imagine a train where each carriage connects to the one before and after it. Adding a new carriage at the front means hooking it before the first carriage and updating the connections so the train starts with the new one.

null <- [New Node] <-> [Old Head] <-> [Second Node] <-> ... <-> null

Steps:
1. New Node's next points to Old Head
2. Old Head's prev points to New Node
3. New Node's prev is null
4. Head pointer updated to New Node

Build-Up - 7 Steps

1

Foundation

Understanding Doubly Linked List Structure

Concept: Learn what a doubly linked list node contains and how nodes connect forward and backward.

A doubly linked list node has three parts: data, a pointer to the next node, and a pointer to the previous node. The list has a head pointer to the first node and a tail pointer to the last node. Each node connects to neighbors both ways, allowing easy forward and backward traversal.

Result

You can visualize the list as a chain where each link knows its neighbors on both sides.

Understanding the two-way connections is key to manipulating the list without losing links or causing errors.

2

Foundation

Creating a New Node in TypeScript

Concept: How to define and create a new node object with data and pointers.

In TypeScript, define a class Node with properties: data (number), next (Node or null), and prev (Node or null). To create a new node, instantiate this class with the data value and set next and prev to null initially.

Result

You get a standalone node ready to be linked into a list.

Knowing how to create nodes is the first step before linking them into the list.

3

Intermediate

Linking New Node at List Start

🤔Before reading on: When inserting at the beginning, do you think we update the old head's prev pointer before or after setting the new node's next pointer? Commit to your answer.

Concept: Learn the order of pointer updates to safely insert the new node at the front.

To insert at the beginning: 1. Set newNode.next to current head. 2. If head exists, set head.prev to newNode. 3. Set newNode.prev to null. 4. Update head pointer to newNode. This order prevents losing references and keeps the list intact.

Result

The new node becomes the first node, linked properly to the rest.

The order of pointer updates is crucial to avoid breaking the list or losing nodes.

4

Intermediate

Handling Empty List Case

🤔Before reading on: If the list is empty, do you think the new node's next and prev pointers should point to itself or null? Commit to your answer.

Concept: Special case when the list has no nodes; the new node becomes the only node.

If the list is empty (head is null), then: - Set newNode.next to null - Set newNode.prev to null - Set head to newNode This means the new node stands alone with no neighbors.

Result

The list now contains one node, correctly initialized.

Handling empty lists prevents null pointer errors and ensures the list starts correctly.

5

Intermediate

Updating Head Pointer Correctly

Concept: The head pointer must always point to the first node after insertion.

After linking the new node, update the list's head pointer to point to the new node. This ensures all future operations start from the correct first node.

Result

The list's head always reflects the current first node.

Maintaining the head pointer is essential for list integrity and correct traversal.

6

Advanced

TypeScript Implementation with Safety Checks

🤔Before reading on: Should the insert function check if the input data is valid or just insert blindly? Commit to your answer.

Concept: Implement the insertion method with TypeScript classes and null checks to avoid runtime errors.

class Node { data: number; next: Node | null = null; prev: Node | null = null; constructor(data: number) { this.data = data; } } class DoublyLinkedList { head: Node | null = null; insertAtBeginning(data: number): void { const newNode = new Node(data); if (this.head === null) { this.head = newNode; return; } newNode.next = this.head; this.head.prev = newNode; newNode.prev = null; this.head = newNode; } } // Example usage: const list = new DoublyLinkedList(); list.insertAtBeginning(10); list.insertAtBeginning(20); list.insertAtBeginning(30); // List order: 30 <-> 20 <-> 10

Result

The list correctly updates with new nodes at the front: 30 <-> 20 <-> 10

Implementing with safety checks prevents errors and ensures the list remains consistent.

7

Expert

Performance and Memory Considerations

🤔Before reading on: Do you think inserting at the beginning of a doubly linked list takes constant time or time proportional to the list size? Commit to your answer.

Concept: Understand the time complexity and memory impact of insertion at the beginning.

Insertion at the beginning is O(1) time because it only changes a few pointers, regardless of list size. Memory-wise, each node requires extra space for two pointers compared to singly linked lists. This tradeoff allows fast bidirectional traversal and insertion.

Result

Insertion is fast and predictable, but memory use is higher than singly linked lists.

Knowing the performance helps choose the right data structure for your needs.

Under the Hood

Each node stores two pointers: one to the next node and one to the previous node. When inserting at the beginning, the new node's next pointer is set to the current head, and if the head exists, its prev pointer is updated to the new node. The new node's prev pointer is null because it becomes the first node. Finally, the head pointer of the list is updated to the new node. This pointer manipulation maintains the bidirectional links without losing any nodes.

Why designed this way?

Doubly linked lists were designed to allow easy traversal in both directions and efficient insertion or deletion at both ends. The two pointers per node enable this flexibility. Inserting at the beginning updates only a few pointers, making it a constant-time operation. Alternatives like singly linked lists only have one pointer per node, making backward traversal or certain insertions slower or impossible.

List before insertion:
null <- [Head Node] <-> [Node 2] <-> [Node 3] -> null

Insert new node:

Step 1: newNode.next = head
Step 2: head.prev = newNode
Step 3: newNode.prev = null
Step 4: head = newNode

List after insertion:
null <- [newNode] <-> [Old Head] <-> [Node 2] <-> [Node 3] -> null

Myth Busters - 3 Common Misconceptions

Quick: When inserting at the beginning, do you think you must update the tail pointer? Commit yes or no.

Common Belief: Many think inserting at the beginning always requires updating the tail pointer.

Reality: The tail pointer only changes if the list was empty before insertion. Otherwise, it remains the same.

Why it matters: Updating the tail unnecessarily can cause bugs or wasted operations, especially in large lists.

Quick: Do you think the new node's prev pointer should point to the old head? Commit yes or no.

Common Belief: Some believe the new node's prev pointer should point to the old head node.

Reality: The new node's prev pointer must be null because it becomes the first node with no previous node.

Why it matters: Incorrect prev pointers break backward traversal and can cause runtime errors.

Quick: Do you think inserting at the beginning requires traversing the whole list? Commit yes or no.

Common Belief: Some assume insertion at the beginning requires walking through the list to find the start.

Reality: Insertion at the beginning is a constant-time operation using the head pointer directly.

Why it matters: Thinking it requires traversal leads to inefficient code and misunderstanding of linked list operations.

Expert Zone

1

When the list is empty, both head and tail pointers must be updated to the new node to maintain list integrity.

2

Pointer updates must be done in a precise order to avoid losing references and causing memory leaks or dangling pointers.

3

In concurrent environments, insertion at the beginning requires synchronization to prevent race conditions on the head pointer.

When NOT to use

If you need only forward traversal and want to save memory, use a singly linked list instead. For random access or frequent middle insertions, arrays or balanced trees are better choices.

Production Patterns

In real systems, doubly linked lists with insertion at the beginning are used in undo-redo stacks, browser history management, and task scheduling where recent items are accessed first.

Connections

Stack Data Structure

Insertion at the beginning of a doubly linked list mimics pushing onto a stack.

Understanding this connection helps implement stack operations efficiently using linked lists.

Memory Management

Pointer updates in linked lists relate closely to how memory addresses are managed and referenced.

Knowing how pointers work aids in understanding low-level memory operations and debugging pointer-related bugs.

Train Carriage Coupling

The bidirectional links in a doubly linked list are like coupling train carriages front and back.

This real-world connection helps grasp the importance of maintaining links in both directions for smooth traversal.

Common Pitfalls

#1 Forgetting to update the old head's prev pointer causes broken backward links.

Wrong approach:

newNode.next = head;
head = newNode; // Missing head.prev = newNode

Correct approach:

newNode.next = head;
head.prev = newNode;
head = newNode;

Root cause:

Not realizing that the old head must know its new previous node to maintain the doubly linked structure.

#2 Not handling empty list case leads to null pointer errors.

Wrong approach:

newNode.next = head;
head.prev = newNode;
head = newNode; // head is null here, so head.prev causes error

Correct approach:

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

Root cause:

Assuming the list always has nodes and not checking for null head.

#3 Setting newNode.prev to old head instead of null breaks list start.

Wrong approach:

newNode.prev = head; // Incorrect, should be null
newNode.next = head;
head.prev = newNode;
head = newNode;

Correct approach:

newNode.prev = null;
newNode.next = head;
head.prev = newNode;
head = newNode;

Root cause:

Misunderstanding that the first node's prev pointer must be null.

Key Takeaways

Inserting at the beginning of a doubly linked list involves creating a new node and carefully updating pointers to maintain bidirectional links.

The new node's next pointer links to the old head, and the old head's prev pointer must point back to the new node.

Handling the empty list case separately prevents runtime errors and ensures the list starts correctly.

This insertion operation runs in constant time, making it efficient for adding items at the front.

Maintaining the head pointer correctly is essential for list integrity and future operations.

Practice

1. What is the main purpose of inserting a node at the beginning of a doubly linked list?

easy

A. To reverse the entire list

B. To add a new node after the tail node

C. To delete the first node in the list

D. To add a new node before the current head node

Solution

1. Step 1: Understand the head node position

   The head node is the first node in the doubly linked list.

2. Step 2: Insert new node before head

   Inserting at the beginning means placing the new node before the current head, making it the new head.

3. Final Answer:

   To add a new node before the current head node -> Option D

4. Quick Check:

   Insert at beginning = add before head [OK]

Hint: Beginning means before the head node [OK]

Common Mistakes:

• Confusing insertion at beginning with insertion at end
• Thinking insertion deletes nodes
• Mixing up head and tail nodes

2. Which of the following TypeScript code snippets correctly creates a new node and inserts it at the beginning of a doubly linked list?

easy

A. newNode.next = head; if(head) head.prev = newNode; head = newNode;

B. newNode.prev = head; if(head) head.next = newNode; head = newNode;

C. newNode.next = null; head = newNode; newNode.prev = null;

D. head = newNode; newNode.next = head; newNode.prev = head;

Solution

1. Step 1: Set newNode.next to current head

   The new node's next pointer should point to the current head node.

2. Step 2: Update current head's prev to newNode if head exists

   If the list is not empty, the current head's prev pointer must point back to the new node.

3. Step 3: Update head to newNode

   Finally, the head pointer is updated to the new node.

4. Final Answer:

   newNode.next = head; if(head) head.prev = newNode; head = newNode; -> Option A

5. Quick Check:

   Set newNode.next=head, head.prev=newNode, head=newNode [OK]

Hint: newNode.next = head; head.prev = newNode; head = newNode [OK]

Common Mistakes:

• Swapping next and prev pointers
• Not updating head pointer
• Setting newNode.prev incorrectly

3. Given the following TypeScript code for a doubly linked list insertion at beginning, what will be the printed list after insertion?

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

let head: Node | null = new Node(10);
head.next = new Node(20);
head.next.prev = head;

const newNode = new Node(5);
newNode.next = head;
head.prev = newNode;
head = newNode;

// Print list
let temp = head;
const result: number[] = [];
while(temp) {
  result.push(temp.data);
  temp = temp.next;
}
console.log(result);

medium

A. [5, 10, 20]

B. [10, 20, 5]

C. [20, 10, 5]

D. [5, 20, 10]

Solution

1. Step 1: Initial list before insertion

   List is 10 <-> 20, head points to 10.

2. Step 2: Insert newNode with data 5 at beginning

   newNode.next = head (10), head.prev = newNode, head = newNode (5).

3. Step 3: Traverse list from new head

   Traverse from 5: 5 -> 10 -> 20.

4. Final Answer:

   [5, 10, 20] -> Option A

5. Quick Check:

   New head 5 followed by 10 and 20 [OK]

Hint: New node becomes head, list order starts with new node [OK]

Common Mistakes:

• Not updating head to newNode
• Incorrectly linking prev pointers
• Printing list from old head

4. Identify the error in the following TypeScript code that attempts to insert a node at the beginning of a doubly linked list:

const newNode = new Node(15);
newNode.prev = null;
newNode.next = head;
head.prev = newNode;
head = newNode;

medium

A. newNode.prev should point to head

B. Missing check if head is null before accessing head.prev

C. head should be assigned before setting newNode.next

D. newNode.next should be null

Solution

1. Step 1: Check if head is null before accessing head.prev

   If the list is empty (head is null), accessing head.prev causes an error.

2. Step 2: Add condition to update head.prev only if head exists

   Use if(head) head.prev = newNode; to avoid runtime error.

3. Final Answer:

   Missing check if head is null before accessing head.prev -> Option B

4. Quick Check:

   Always check head before head.prev [OK]

Hint: Check if head exists before accessing its properties [OK]

Common Mistakes:

• Ignoring null head and causing runtime error
• Swapping next and prev pointers
• Assigning head too early

5. You have a doubly linked list with nodes containing values [30, 40, 50]. You want to insert a new node with value 20 at the beginning. After insertion, which of the following correctly represents the list and the pointers of the new head node?

hard

A. List: 20 <-> 30 <-> 40 <-> 50; new head prev points to 30, next = null

B. List: 30 <-> 40 <-> 50 <-> 20; new head prev = 50, next = null

C. List: 20 <-> 30 <-> 40 <-> 50; new head prev = null, next points to 30

D. List: 50 <-> 40 <-> 30 <-> 20; new head prev = null, next points to 40

Solution

1. Step 1: Insert new node with value 20 before current head 30

   New node becomes head, its prev is null, next points to old head (30).

2. Step 2: Update old head's prev to new node

   Old head (30) prev pointer updated to new node (20).

3. Step 3: Confirm list order and pointers

   List order is 20 <-> 30 <-> 40 <-> 50 with new head prev=null, next=30.

4. Final Answer:

   List: 20 <-> 30 <-> 40 <-> 50; new head prev = null, next points to 30 -> Option C

5. Quick Check:

   New head prev=null, next=old head [OK]

Hint: New head prev always null, next points to old head [OK]

Common Mistakes:

• Setting new head prev to old tail
• Reversing list order accidentally
• Not updating old head prev pointer