Insert at Specific Position in Doubly Linked List in DSA Typescript - Deep Dive

Overview - Insert at Specific Position in 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 node. Inserting at a specific position means adding a new node exactly where you want in this chain, shifting others as needed. This operation helps keep the list organized and flexible. It allows you to add data anywhere, not just at the start or end.

Why it matters

Without the ability to insert at specific positions, you would be stuck adding data only at the ends, which limits how you organize information. Many real-world tasks, like editing playlists or managing tasks, need precise placement. This operation makes the list adaptable and efficient for such uses. Without it, data handling would be slower and more complicated.

Where it fits

Before learning this, you should understand what a doubly linked list is and how nodes connect. After this, you can learn about deleting nodes at specific positions or advanced list operations like sorting or reversing. This topic builds your skill in managing linked data structures step-by-step.

Mental Model

Core Idea

Inserting at a specific position in a doubly linked list means carefully linking a new node between two existing nodes so the chain stays connected both forwards and backwards.

Think of it like...

Imagine a train where each carriage is connected to the one before and after it. Inserting a new carriage in the middle means unhooking the two carriages where you want to add, placing the new one between them, and hooking all three together again.

Head ⇄ Node1 ⇄ Node2 ⇄ Node3 ⇄ Tail

To insert newNode at position 2:

Before:
Head ⇄ Node1 ⇄ Node2 ⇄ Node3 ⇄ Tail

After:
Head ⇄ Node1 ⇄ newNode ⇄ Node2 ⇄ Node3 ⇄ Tail

Build-Up - 7 Steps

1

Foundation

Understanding Doubly Linked List Structure

Concept: Learn how nodes in a doubly linked list connect to both previous and next nodes.

A doubly linked list node has three parts: data, a pointer to the previous node, and a pointer to the next node. The list starts with a head node and ends with a tail node. Each node connects forward and backward, allowing easy movement in both directions.

Result

You can move through the list from start to end and back, visiting each node in order.

Understanding the two-way connections is essential because insertion must update both previous and next links to keep the list intact.

2

Foundation

Basic Node Insertion at Ends

Concept: Learn how to add a new node at the start or end of the list.

To insert at the start, create a new node, set its next to the current head, and update the head's previous to this new node. Then update the head pointer. To insert at the end, create a new node, set its previous to the current tail, update the tail's next to this new node, and update the tail pointer.

Result

The list grows by one node at the chosen end, maintaining correct forward and backward links.

Mastering end insertions builds the foundation for inserting anywhere, as the same link updates apply but in the middle.

3

Intermediate

Locating the Target Position

🤔Before reading on: do you think you should count nodes from the head or tail to find the position? Commit to your answer.

Concept: To insert at a specific position, first find the node currently at that position or the node after which you want to insert.

Start from the head and move forward, counting nodes until you reach the position just before where the new node will go. If the position is 1, it means inserting at the start. If the position is beyond the list length, handle it as an error or insert at the end.

Result

You identify the exact spot in the list where the new node should be linked.

Knowing how to find the correct node ensures the insertion happens exactly where intended, preventing list corruption.

4

Intermediate

Adjusting Links for Middle Insertion

🤔Before reading on: do you think you need to update one or two nodes' pointers when inserting in the middle? Commit to your answer.

Concept: Inserting in the middle requires updating the previous node's next pointer and the next node's previous pointer to include the new node.

Once you find the node after which to insert, create the new node. Set its previous pointer to that node and its next pointer to that node's next. Then update the next node's previous pointer to the new node and the previous node's next pointer to the new node.

Result

The new node is linked correctly between two existing nodes, preserving the list's two-way chain.

Updating both forward and backward links is crucial to maintain the list's integrity and allow traversal in both directions.

5

Intermediate

Handling Edge Cases in Insertion

🤔Before reading on: do you think inserting at position 0 is valid or should be handled specially? Commit to your answer.

Concept: Positions outside the valid range or at the ends require special handling to avoid errors.

If the position is less than 1, treat it as inserting at the start. If the position is greater than the list length plus one, reject or insert at the end. Also, handle empty lists by setting head and tail to the new node.

Result

Insertion works safely even when given unusual positions or empty lists.

Anticipating and managing edge cases prevents crashes and unexpected behavior in real applications.

6

Advanced

TypeScript Implementation with Safety Checks

🤔Before reading on: do you think TypeScript's type system helps prevent pointer errors in linked lists? Commit to your answer.

Concept: Implement the insertion method in TypeScript with clear types and checks to avoid runtime errors.

Define a Node class with data, prev, and next pointers. Define a DoublyLinkedList class with head and tail. Implement insertAtPosition(position: number, data: T) that: - Checks position validity - Handles empty list - Finds the correct node - Updates pointers carefully Example code: class Node { data: T; prev: Node | null = null; next: Node | null = null; constructor(data: T) { this.data = data; } } class DoublyLinkedList { head: Node | null = null; tail: Node | null = null; insertAtPosition(position: number, data: T): void { if (position < 1) position = 1; const newNode = new Node(data); if (!this.head) { this.head = this.tail = newNode; return; } if (position === 1) { newNode.next = this.head; this.head.prev = newNode; this.head = newNode; return; } let current = this.head; let index = 1; while (current.next && index < position - 1) { current = current.next; index++; } if (!current.next) { current.next = newNode; newNode.prev = current; this.tail = newNode; } else { newNode.next = current.next; newNode.prev = current; current.next.prev = newNode; current.next = newNode; } } printList(): void { let current = this.head; const result: string[] = []; while (current) { result.push(String(current.data)); current = current.next; } console.log(result.join(' ⇄ ')); } } // Example usage: const list = new DoublyLinkedList(); list.insertAtPosition(1, 10); list.insertAtPosition(2, 20); list.insertAtPosition(2, 15); list.printList();

Result

Output: 10 ⇄ 15 ⇄ 20 The new node with data 15 is inserted at position 2 correctly.

Using TypeScript's types and careful checks reduces bugs and makes the code easier to understand and maintain.

7

Expert

Performance and Memory Considerations

🤔Before reading on: do you think insertion at a specific position in a doubly linked list is always fast? Commit to your answer.

Concept: Understand the time and memory costs of insertion and how to optimize for large lists.

Insertion requires locating the position, which takes O(n) time because you may need to traverse the list. The actual pointer updates are O(1). For very large lists, consider maintaining additional pointers or using balanced trees for faster access. Also, each node stores two pointers, doubling memory compared to singly linked lists.

Result

You realize insertion speed depends on position and list size, and memory use is higher than simpler lists.

Knowing these tradeoffs helps choose the right data structure and optimize performance in real systems.

Under the Hood

Each node in a doubly linked list holds two pointers: one to the previous node and one to the next. Inserting a node at a specific position involves updating four pointers: the new node's prev and next, the previous node's next, and the next node's prev. This maintains the bidirectional chain. The list head and tail pointers may also update if insertion is at the ends.

Why designed this way?

Doubly linked lists were designed to allow easy forward and backward traversal. The two pointers per node enable this but require careful pointer updates during insertion to avoid breaking the chain. This design balances flexibility with memory cost, unlike singly linked lists which only allow one-way traversal.

┌───────┐     ┌───────┐     ┌───────┐
│ Node1 │ ⇄ │ Node2 │ ⇄ │ Node3 │
└───────┘     └───────┘     └───────┘

Insert newNode between Node1 and Node2:

Before:
Node1.next -> Node2
Node2.prev -> Node1

After:
Node1.next -> newNode
newNode.prev -> Node1
newNode.next -> Node2
Node2.prev -> newNode

Myth Busters - 4 Common Misconceptions

Quick: When inserting at position 1, do you only need to update the head pointer? Commit to yes or no.

Common Belief: People often think inserting at the start only requires changing the head pointer.

Reality: You must also update the old head's previous pointer to the new node to maintain backward links.

Why it matters: Failing to update the old head's prev pointer breaks backward traversal, causing bugs when moving backward through the list.

Quick: Do you think inserting at a position beyond the list length automatically appends at the end? Commit to yes or no.

Common Belief: Many believe that inserting beyond the list length just adds the node at the end without error.

Reality: Insertion beyond the list length should be handled explicitly; blindly appending can hide bugs or corrupt data if not intended.

Why it matters: Ignoring position validity can cause unexpected list states, making debugging difficult and leading to data inconsistency.

Quick: Is it safe to update only one pointer when inserting in the middle? Commit to yes or no.

Common Belief: Some think updating just the previous node's next pointer is enough when inserting in the middle.

Reality: Both the previous node's next and the next node's prev pointers must be updated to keep the list consistent.

Why it matters: Updating only one pointer breaks the two-way link, causing traversal errors and potential crashes.

Quick: Do you think doubly linked lists always use more memory than singly linked lists? Commit to yes or no.

Common Belief: It's commonly believed doubly linked lists always use twice the memory of singly linked lists.

Reality: While each node stores two pointers, memory overhead depends on node size and system alignment; sometimes the difference is less than double.

Why it matters: Overestimating memory cost may lead to avoiding doubly linked lists even when their benefits outweigh the cost.

Expert Zone

1

When inserting near the tail, starting traversal from the tail node can reduce search time, especially in large lists.

2

Maintaining a size counter in the list class helps quickly validate positions and optimize insertion logic.

3

In concurrent environments, insertion requires careful locking or atomic operations to avoid race conditions and maintain list integrity.

When NOT to use

Avoid using doubly linked lists for very large datasets requiring frequent random access; arrays or balanced trees offer faster indexing. Also, if memory is extremely limited, singly linked lists or other compact structures may be better.

Production Patterns

Doubly linked lists with specific position insertion are used in text editors for managing cursor positions, in undo-redo stacks where bidirectional traversal is needed, and in browser history implementations to move back and forth efficiently.

Connections

Array Insertion

Both involve placing an element at a specific position, but arrays shift elements while linked lists update pointers.

Understanding linked list insertion clarifies why arrays have costly shifts, highlighting tradeoffs between data structures.

Undo-Redo Systems

Doubly linked lists model undo-redo stacks by allowing movement forward and backward through states.

Knowing insertion in doubly linked lists helps grasp how undo-redo operations add or remove states at specific points.

Train Carriage Coupling

The physical coupling and uncoupling of train carriages mirrors pointer updates in doubly linked list insertion.

This cross-domain connection shows how careful linking maintains system integrity, whether in software or real-world mechanics.

Common Pitfalls

#1 Forgetting to update the previous pointer of the node after the inserted node.

Wrong approach:

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

Correct approach:

newNode.next = current.next;
newNode.prev = current;
current.next.prev = newNode;
current.next = newNode;

Root cause:

Not realizing the list is doubly linked and both forward and backward pointers must be updated.

#2 Inserting at position 1 without updating the old head's previous pointer.

Wrong approach:

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

Correct approach:

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

Root cause:

Treating the list like a singly linked list and ignoring backward links.

#3 Not handling empty list case, causing null pointer errors.

Wrong approach:

if (position === 1) {
newNode.next = head;
head.prev = newNode;
head = newNode;
} // head might be null here

Correct approach:

if (!head) {
head = tail = newNode;
return;
}
if (position === 1) {
newNode.next = head;
head.prev = newNode;
head = newNode;
}

Root cause:

Assuming the list is never empty and not checking for null pointers.

Key Takeaways

Inserting at a specific position in a doubly linked list requires updating four pointers to maintain the two-way chain.

Finding the correct position involves traversing the list, which takes time proportional to the position number.

Edge cases like empty lists and invalid positions must be handled carefully to avoid errors.

TypeScript's type system helps catch pointer mistakes early and makes the code safer and clearer.

Understanding the memory and performance tradeoffs guides when to use doubly linked lists versus other data structures.

Practice

1. What does inserting a node at a specific position in a doubly linked list involve?

easy

A. Adjusting the previous and next pointers of neighboring nodes to include the new node

B. Only changing the head pointer of the list

C. Replacing the node at that position without changing pointers

D. Adding the node at the end regardless of position

Solution

1. Step 1: Understand doubly linked list structure

   Each node has pointers to both previous and next nodes, so insertion requires updating these pointers.

2. Step 2: Insert node at specific position

   We must update the previous node's next pointer and the next node's previous pointer to point to the new node.

3. Final Answer:

   Adjusting the previous and next pointers of neighboring nodes to include the new node -> Option A

4. Quick Check:

   Pointer updates = Adjust neighbors [OK]

Hint: Remember to update both previous and next pointers [OK]

Common Mistakes:

• Only updating one pointer leads to broken links
• Ignoring the previous pointer in insertion
• Replacing nodes instead of inserting

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

easy

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

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

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

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

Solution

1. Step 1: Check for previous and next pointers

   A doubly linked list node must have both next and prev pointers, which can be null.

2. Step 2: Verify constructor initializes all properties

   class Node { value: number; next: Node | null; prev: Node | null; constructor(value: number) { this.value = value; this.next = null; this.prev = null; } } initializes value, next, and prev correctly with proper types.

3. Final Answer:

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

4. Quick Check:

   Both pointers initialized = class Node { value: number; next: Node | null; prev: Node | null; constructor(value: number) { this.value = value; this.next = null; this.prev = null; } } [OK]

Hint: Doubly linked nodes need both next and prev pointers [OK]

Common Mistakes:

• Forgetting to initialize prev pointer
• Using wrong property names
• Not allowing null for next or prev

3. Given the doubly linked list 1 <-> 2 <-> 4 and the code below inserting 3 at position 3, what is the list after insertion?

insertAtPosition(head, 3, 3);

Positions start at 1.

medium

A. 1 <-> 2 <-> 3 <-> 4

B. 1 <-> 3 <-> 2 <-> 4

C. 3 <-> 1 <-> 2 <-> 4

D. 1 <-> 2 <-> 4 <-> 3

Solution

1. Step 1: Identify position 3 in the list

   Positions: 1=1, 2=2, 3=4. We want to insert before node with value 4.

2. Step 2: Insert node with value 3 at position 3

   Update pointers so 2 points next to 3, 3 points prev to 2 and next to 4, 4 points prev to 3.

3. Final Answer:

   1 <-> 2 <-> 3 <-> 4 -> Option A

4. Quick Check:

   Insert at position 3 = 1-2-3-4 [OK]

Hint: Count nodes, insert before node at that position [OK]

Common Mistakes:

• Inserting after instead of before position
• Mixing up prev and next pointers
• Off-by-one errors in position counting

4. What is wrong with this TypeScript code snippet for inserting a node at position 2 in a doubly linked list?

function insertAtPosition(head: Node | null, value: number, position: number): Node | null {
  let newNode = new Node(value);
  if (position === 1) {
    newNode.next = head;
    if (head) head.prev = newNode;
    return newNode;
  }
  let current = head;
  for (let i = 1; i < position - 1; i++) {
    if (!current) return head;
    current = current.next;
  }
  newNode.next = current.next;
  current.next = newNode;
  newNode.prev = current;
  return head;
}

medium

A. Not handling insertion at head

B. Incorrect loop range in for loop

C. Missing update of newNode.next.prev to newNode

D. Not creating new node correctly

Solution

1. Step 1: Analyze pointer updates after insertion

   After inserting newNode, newNode.next.prev should point back to newNode to maintain doubly links.

2. Step 2: Identify missing pointer update

   The code misses updating newNode.next.prev = newNode, which breaks backward link from next node.

3. Final Answer:

   Missing update of newNode.next.prev to newNode -> Option C

4. Quick Check:

   Update both next and prev pointers [OK]

Hint: Always update newNode.next.prev after insertion [OK]

Common Mistakes:

• Forgetting to update newNode.next.prev
• Loop off-by-one errors
• Not handling empty list insertion

5. You have a doubly linked list representing train cars: Engine <-> Car1 <-> Car2 <-> Caboose. You want to insert a new CarX at position 2. After insertion, what is the correct order of cars?

hard

A. CarX <-> Engine <-> Car1 <-> Car2 <-> Caboose

B. Engine <-> CarX <-> Car1 <-> Car2 <-> Caboose

C. Engine <-> Car1 <-> CarX <-> Car2 <-> Caboose

D. Engine <-> Car1 <-> Car2 <-> Caboose <-> CarX

Solution

1. Step 1: Identify position 2 in the list

   Positions: 1=Engine, 2=Car1. Insert CarX before Car1 to become new position 2.

2. Step 2: Insert CarX at position 2

   Update pointers so Engine next points to CarX, CarX prev to Engine, CarX next to Car1, Car1 prev to CarX.

3. Final Answer:

   Engine <-> CarX <-> Car1 <-> Car2 <-> Caboose -> Option B

4. Quick Check:

   Insert at position 2 = Engine-CarX-Car1... [OK]

Hint: Insert before node at position to shift others right [OK]

Common Mistakes:

• Inserting after instead of before position
• Not updating prev pointers correctly
• Confusing position indexing starting at 0