Insert at Specific Position in Doubly Linked List in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a doubly linked list?

A doubly linked list is a chain of nodes where each node has three parts: data, a pointer to the next node, and a pointer to the previous node. This allows moving forward and backward through the list.

beginner

Why do we need to update both next and previous pointers when inserting a node in a doubly linked list?

Because each node points to both its next and previous nodes, when inserting a new node, we must update the next pointer of the previous node and the previous pointer of the next node to keep the list connected correctly.

intermediate

What happens if you try to insert a node at a position greater than the list length in a doubly linked list?

If the position is greater than the list length, the insertion should either fail or add the node at the end of the list, depending on the implementation. Trying to insert beyond the list can cause errors.

beginner

In TypeScript, what type of variable would you use to represent a node in a doubly linked list?

You would use a class or interface with properties for data, next (which points to the next node or null), and prev (which points to the previous node or null).

intermediate

What is the time complexity of inserting a node at a specific position in a doubly linked list?

The time complexity is O(n) because you may need to traverse up to n nodes to reach the desired position before insertion.

What pointers need to be updated when inserting a node at position 3 in a doubly linked list?

A Next pointer of node 3 and previous pointer of node 2

B Next pointer of node 2 and previous pointer of node 3

C Only previous pointer of node 3

D Only next pointer of node 2

When inserting at position 3, the new node goes between nodes 2 and 3. So, update next of node 2 to new node and previous of node 3 to new node.

If you insert a node at position 1 in a doubly linked list, what happens?

A The new node becomes the head of the list

B The new node is added at the end

C The list remains unchanged

D The new node is inserted after the head

Position 1 means the start of the list, so the new node becomes the new head.

What is the previous pointer of the head node in a doubly linked list?

A Undefined

B Points to the last node

C Points to itself

D Null

The head node has no previous node, so its previous pointer is null.

Which of these is NOT a step when inserting a node at a specific position in a doubly linked list?

A Update the head pointer to the new node regardless of position

B Traverse to the node before the insertion point

C Update the new node's next and previous pointers

D Update the adjacent nodes' pointers to include the new node

You only update the head pointer if inserting at position 1. Otherwise, head stays the same.

What is the best way to handle insertion at a position greater than the list length?

A Insert at the head

B Throw an error or ignore the insertion

C Insert at the end of the list

D Replace the last node

Common practice is to insert at the end if position is beyond list length.

Explain step-by-step how to insert a new node at position 3 in a doubly linked list.

Think about how the pointers connect before and after the new node.

Describe how the head and tail pointers change when inserting at the start and end of a doubly linked list.

Remember head and tail mark the ends of the list.

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