Insert at Specific Position in Doubly Linked List in DSA Typescript - Execution Trace

Concept Flow - Insert at Specific Position in Doubly Linked List

Create new node

↓

Check if position is 1

↓

Insert at [Start at head

↓

Traverse to position-1

↓

Adjust pointers: prev, new_node, next

↓

Insertion done

Create a new node, then either insert at head if position is 1, or traverse to the node before the position and adjust pointers to insert the new node.

Execution Sample

DSA Typescript

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

function insertAtPosition(head: Node | null, data: number, pos: number): Node | null {
  let newNode = new Node(data);
  if (pos === 1) {
    newNode.next = head;
    if (head) head.prev = newNode;
    return newNode;
  }
  let current = head;
  let count = 1;
  while (current && count < pos - 1) {
    current = current.next;
    count++;
  }
  if (!current) return head;
  newNode.next = current.next;
  if (current.next) current.next.prev = newNode;
  current.next = newNode;
  newNode.prev = current;
  return head;
}

This code inserts a new node with given data at a specific position in a doubly linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=99	1 -> 2 -> 3 -> 4 -> null	None	1 <-> 2 <-> 3 <-> 4 <-> null
2	Check if position=1 (No)	1 -> 2 -> 3 -> 4 -> null	None	1 <-> 2 <-> 3 <-> 4 <-> null
3	Traverse to node at position 2 (pos-1)	1 -> 2 -> 3 -> 4 -> null	current points to node with data=2	1 <-> 2 <-> 3 <-> 4 <-> null
4	Adjust pointers to insert new node after node 2	1 -> 2 -> 99 -> 3 -> 4 -> null	2.next = 99; 99.prev = 2; 99.next = 3; 3.prev = 99	1 <-> 2 <-> 99 <-> 3 <-> 4 <-> null
5	Return head	1 -> 2 -> 99 -> 3 -> 4 -> null	None	1 <-> 2 <-> 99 <-> 3 <-> 4 <-> null
6	Exit	1 -> 2 -> 99 -> 3 -> 4 -> null	None	1 <-> 2 <-> 99 <-> 3 <-> 4 <-> null

💡 Insertion done at position 3, traversal stopped at node 2

Variable Tracker

Variable	Start	After Step 3	After Step 4	Final
head	Node(1)	Node(1)	Node(1)	Node(1)
newNode	Node(99)	Node(99)	Node(99)	Node(99)
current	Node(1)	Node(2)	Node(2)	Node(2)
count	1	2	2	2

Key Moments - 3 Insights

Why do we stop traversal at position-1 and not at the exact position?

Because we need to insert the new node after the node at position-1, so we stop traversal there to adjust pointers correctly (see execution_table step 3 and 4).

What happens if the position is 1?

The new node becomes the new head, its next points to the old head, and the old head's prev points back to the new node (see concept_flow and execution_sample).

Why do we check if current.next exists before setting current.next.prev?

Because if current.next is null (inserting at end), we must not access prev of null to avoid errors (see execution_table step 4).

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what node does 'current' point to?

A Node with data=2

B Node with data=3

C Node with data=1

D Node with data=99

💡 Hint

Check the 'Pointer Changes' column at step 3 in execution_table

At which step does the new node get linked into the list?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look for pointer adjustments involving newNode in execution_table

If we insert at position 1, what will be the new head's data?

A Null

B Data of old head

C Data of new node

D Data of node at position 2

💡 Hint

Refer to concept_flow and execution_sample for position=1 case

Concept Snapshot

Insert at Specific Position in Doubly Linked List:
- Create new node
- If position=1, insert at head
- Else traverse to position-1
- Adjust prev and next pointers
- Handle edge cases (empty list, end insertion)
- Return head of updated list

Full Transcript

To insert a node at a specific position in a doubly linked list, first create the new node. If the position is 1, insert the new node at the head by adjusting the new node's next pointer to the old head and the old head's prev pointer to the new node. Otherwise, traverse the list to the node just before the desired position. Then, adjust the pointers: set the new node's next to the current node's next, update the next node's prev to the new node if it exists, set the current node's next to the new node, and set the new node's prev to the current node. Finally, return the head of the list. This process ensures the doubly linked list remains connected correctly after insertion.

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