Insert at Specific Position in Doubly Linked List in DSA Typescript

Mental Model

A doubly linked list lets you move forward and backward through nodes. To insert at a position, you find that spot and link the new node between its neighbors.

Analogy: Imagine a train with cars connected front and back. To add a new car in the middle, you disconnect the two cars where you want to insert, then connect the new car between them.

null ← 1 ↔ 2 ↔ 3 -> null
           ↑
       head pointer

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3, insert value 4 at position 2

Goal: Insert the value 4 between nodes 1 and 2, so the list becomes 1 ↔ 4 ↔ 2 ↔ 3

Step 1: start at head node 1

null ← [1↑] ↔ 2 ↔ 3 -> null

Why: We begin traversal from the head to find the insertion point

Step 2: traversal stops at node 1 (position 1, before insertion point)

null ← [1↑] ↔ 2 ↔ 3 -> null

Why: We traverse while currentPosition < position - 1 (1 < 1? false), stopping at the node before the insertion point

Step 3: create new node 4 and link it between 1 and 2

null ← 1 ↔ [4] ↔ 2 ↔ 3 -> null

Why: We insert new node 4 by adjusting next and prev pointers of neighbors

Result:

null ← 1 ↔ 4 ↔ 2 ↔ 3 -> null

Annotated Code

DSA Typescript

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

class DoublyLinkedList {
  head: Node | null;
  constructor() {
    this.head = null;
  }

  insertAtPosition(value: number, position: number): void {
    const newNode = new Node(value);
    if (position === 1) {
      // Insert at head
      newNode.next = this.head;
      if (this.head) {
        this.head.prev = newNode;
      }
      this.head = newNode;
      return;
    }

    let current = this.head;
    let currentPosition = 1;

    // Traverse to the node before the insertion point
    while (current && currentPosition < position - 1) {
      current = current.next;
      currentPosition++;
    }

    if (!current) {
      // Position is beyond list length, append at end
      let tail = this.head;
      if (!tail) {
        this.head = newNode;
        return;
      }
      while (tail.next) {
        tail = tail.next;
      }
      tail.next = newNode;
      newNode.prev = tail;
      return;
    }

    // Insert newNode after current
    newNode.next = current.next;
    newNode.prev = current;
    if (current.next) {
      current.next.prev = newNode;
    }
    current.next = newNode;
  }

  printList(): void {
    let current = this.head;
    let result = '';
    while (current) {
      result += current.value + ' ↔ ';
      current = current.next;
    }
    result += 'null';
    console.log(result);
  }
}

// Driver code
const dll = new DoublyLinkedList();
dll.insertAtPosition(1, 1); // list: 1
dll.insertAtPosition(2, 2); // list: 1 ↔ 2
dll.insertAtPosition(3, 3); // list: 1 ↔ 2 ↔ 3

// Insert 4 at position 2
dll.insertAtPosition(4, 2);
dll.printList();

if (position === 1) { ... }

handle insertion at the head by adjusting head pointer and neighbors

while (current && currentPosition < position - 1) { current = current.next; currentPosition++; }

traverse to node before insertion position

if (!current) { ... }

if position beyond list length, append at end

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

link new node's next and prev pointers

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

update next node's prev pointer to new node

current.next = newNode;

link current node's next pointer to new node

Output

1 ↔ 4 ↔ 2 ↔ 3 ↔ null

Complexity Analysis

Time: O(n) because we may need to traverse up to n nodes to reach the insertion position

Space: O(1) because we only create one new node and use a few pointers

vs Alternative: Compared to inserting in an array which may require shifting elements (O(n)), doubly linked list insertion only needs pointer updates (O(1) after traversal)

Edge Cases

insert at position 1 in empty list

new node becomes head with no next or prev

DSA Typescript

if (position === 1) { ... }

insert at position beyond list length

new node is appended at the end

DSA Typescript

if (!current) { ... }

insert in middle of list

new node links between two existing nodes

DSA Typescript

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

When to Use This Pattern

When you need to add an element at a specific place in a list that allows moving both forward and backward, use the insert at position pattern in doubly linked lists to efficiently update pointers.

Common Mistakes

Mistake: Not updating the prev pointer of the node after the inserted node
Fix: Always set current.next.prev = newNode if current.next exists

Mistake: Not handling insertion at head separately
Fix: Check if position is 1 and update head pointer accordingly

Mistake: Not handling insertion beyond list length
Fix: If traversal reaches null before position, append at the end

Summary

Inserts a new node at a given position in a doubly linked list by adjusting next and prev pointers.

Use when you want to add elements anywhere in a doubly linked list, not just at ends.

The key is to carefully update four pointers: new node's next and prev, and neighbors' prev and next.

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