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

Concept Flow - Insert at Specific Position in Doubly Linked List

Create new node with value

↓

Check if position is 1

↓

Insert at head

↓

Traverse to position-1 node

↓

Adjust pointers: new node prev and next

↓

Adjust adjacent nodes pointers

↓

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 C++

void insertAtPosition(Node*& head, int pos, int val) {
  Node* newNode = new Node(val);
  if (pos == 1) {
    newNode->next = head;
    if (head) head->prev = newNode;
    head = newNode;
    return;
  }
  Node* temp = head;
  for (int i = 1; i < pos - 1 && temp; i++) temp = temp->next;
  if (!temp) return;
  newNode->next = temp->next;
  if (temp->next) temp->next->prev = newNode;
  temp->next = newNode;
  newNode->prev = temp;
}

This code inserts a new node with value val at position pos in a doubly linked list starting at head.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with value 10	10	newNode created with val=10	10 <-> null
2	Check if position == 1	10	pos=3, so No	10 <-> null
3	Start at head (node with val=5)	5 <-> 15	temp points to node val=5	5 <-> 15 <-> null
4	Traverse to position-1 (pos=3, so move 1 step)	5 <-> 15	temp moves to node val=15	5 <-> 15 <-> null
5	Adjust newNode pointers	5 <-> 15	newNode->next = temp->next (null), newNode->prev = temp (15)	5 <-> 15 <-> 10 <-> null
6	Adjust adjacent nodes pointers	5 <-> 15	temp->next = newNode, no next node to update prev	5 <-> 15 <-> 10 <-> null
7	Insertion done	5 <-> 15 <-> 10	head unchanged	5 <-> 15 <-> 10 <-> null
8	Exit	5 <-> 15 <-> 10	Insertion complete	5 <-> 15 <-> 10 <-> null

💡 Reached position 3, inserted new node with value 10, no further traversal needed.

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	After Step 6	Final
head	5	5	5	5	5	5
temp	5	5	15	15	15	15
newNode	null	null	null	10	10	10
pos	3	3	3	3	3	3

Key Moments - 3 Insights

Why do we check if position == 1 separately?

Because inserting at position 1 means inserting at the head, which requires updating the head pointer and possibly the previous head's prev pointer. This is shown in step 2 where we decide the insertion method.

What happens if the position is beyond the list length?

In the code, if temp becomes null before reaching position-1, the function returns without insertion. This prevents invalid memory access, as seen in step 4 where traversal stops if temp is null.

Why do we update both next and prev pointers when inserting?

Because it's a doubly linked list, each node has pointers to both previous and next nodes. To maintain list integrity, we must update newNode's next and prev, and also adjust adjacent nodes' pointers, as shown in steps 5 and 6.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of temp after step 4?

A Node with value 5

B Node with value 15

C Node with value 10

D Null

💡 Hint

Check the 'Pointer Changes' column in step 4 of the execution_table.

At which step is the new node's prev pointer set?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Adjust newNode pointers' operation in the execution_table.

If position was 1, which pointer would be updated to point to the new node?

A temp->next

B head

C newNode->next

D newNode->prev

💡 Hint

Refer to the concept_flow where position == 1 leads to inserting at head.

Concept Snapshot

Insert at Specific Position in Doubly Linked List:
- Create new node with given value
- If position == 1, insert at head and update head pointer
- Else, traverse to node at position-1
- Adjust new node's next and prev pointers
- Update adjacent nodes' pointers to include new node
- Handle edge cases like position beyond list length

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 at the head by updating the new node's next pointer to the current head and updating the head's prev pointer if it exists, then update the head pointer to the new node. Otherwise, start from the head and traverse to the node just before the desired position. If this node exists, adjust the new node's next pointer to the next node of the current node, and its prev pointer to the current node. Then update the current node's next pointer to the new node, and if the next node exists, update its prev pointer to the new node. This maintains the doubly linked list structure. If the position is beyond the list length, no insertion occurs. This process ensures the list remains connected correctly in both directions after insertion.

Practice

1. What happens when you insert a new node at position 1 in a doubly linked list?

easy

A. The list remains unchanged.

B. The new node becomes the new head of the list.

C. The new node replaces the last node.

D. The new node is added at the end of the list.

Solution

1. Step 1: Understand position 1 in doubly linked list

   Position 1 means the start of the list, so the new node should be the first node.

2. Step 2: Insert new node at head

   The new node's next pointer points to the old head, and the old head's previous pointer points back to the new node.

3. Final Answer:

   The new node becomes the new head of the list. -> Option B

4. Quick Check:

   Insert at position 1 = new head [OK]

Hint: Position 1 means insert at the start [OK]

Common Mistakes:

• Inserting at position 1 but not updating head pointer
• Not updating previous pointer of old head
• Confusing position 1 with end of list

2. Which of the following is the correct syntax to insert a new node at position pos in a doubly linked list in C++?

easy

A. newNode->next = temp->next; temp->next->prev = newNode; temp->next = newNode; newNode->prev = temp;

B. newNode->prev = temp->prev; temp->prev->next = newNode; temp->prev = newNode; newNode->next = temp;

C. newNode->next = temp->prev; temp->prev->prev = newNode; temp->prev = newNode; newNode->prev = temp;

D. newNode->prev = temp->next; temp->next->next = newNode; temp->next = newNode; newNode->next = temp;

Solution

1. Step 1: Identify correct pointer updates for insertion

   When inserting after temp, newNode's next points to temp's next, and newNode's prev points to temp.

2. Step 2: Update surrounding nodes' pointers

   temp's next's prev must point to newNode, and temp's next must point to newNode.

3. Final Answer:

   newNode->next = temp->next; temp->next->prev = newNode; temp->next = newNode; newNode->prev = temp; -> Option A

4. Quick Check:

   Correct pointer updates = newNode->next = temp->next; temp->next->prev = newNode; temp->next = newNode; newNode->prev = temp; [OK]

Hint: Update next and prev pointers carefully [OK]

Common Mistakes:

• Mixing up next and prev pointers
• Not updating temp->next->prev pointer
• Assigning pointers in wrong order causing broken links

3. Given the doubly linked list: 10 <-> 20 <-> 30 <-> null, what will be the list after inserting 15 at position 2?

void insertAtPosition(Node*& head, int data, int pos) {
  Node* newNode = new Node(data);
  if (pos == 1) {
    newNode->next = head;
    if (head) head->prev = newNode;
    head = newNode;
    return;
  }
  Node* temp = head;
  for (int i = 1; i < pos - 1 && temp != nullptr; i++) {
    temp = temp->next;
  }
  if (temp == nullptr) return;
  newNode->next = temp->next;
  if (temp->next) temp->next->prev = newNode;
  temp->next = newNode;
  newNode->prev = temp;
}

medium

A. 10 <-> 15 <-> 20 <-> 30 <-> null

B. 15 <-> 10 <-> 20 <-> 30 <-> null

C. 10 <-> 20 <-> 15 <-> 30 <-> null

D. 10 <-> 20 <-> 30 <-> 15 <-> null

Solution

1. Step 1: Locate position 2 in the list

   Position 2 means after the first node (10). So temp points to node with data 10.

2. Step 2: Insert new node with data 15 after temp

   New node's next points to 20, and prev points to 10. Update 10's next to new node and 20's prev to new node.

3. Final Answer:

   10 <-> 15 <-> 20 <-> 30 <-> null -> Option A

4. Quick Check:

   Insert at position 2 places new node after first node [OK]

Hint: Position 2 means insert after first node [OK]

Common Mistakes:

• Inserting before first node instead of after
• Not updating prev pointer of next node
• Skipping position count in loop

4. Identify the error in the following code snippet for inserting at position pos in a doubly linked list:

void insertAtPosition(Node*& head, int data, int pos) {
  Node* newNode = new Node(data);
  if (pos == 1) {
    newNode->next = head;
    if (head) head->prev = newNode;
    head = newNode;
    return;
  }
  Node* temp = head;
  for (int i = 1; i < pos - 1; i++) {
    temp = temp->next;
  }
  newNode->next = temp->next;
  temp->next = newNode;
  newNode->prev = temp;
  if (newNode->next) newNode->next->prev = newNode;
}

medium

A. The newNode->next pointer is assigned after temp->next is changed.

B. The newNode->prev pointer is not set correctly.

C. The head pointer is not updated when inserting at position 1.

D. The loop does not check if temp is nullptr, causing possible crash.

Solution

1. Step 1: Analyze the for loop traversal

   The loop moves temp forward but does not check if temp becomes nullptr, risking null pointer dereference.

2. Step 2: Identify missing safety check

   Without checking temp != nullptr, accessing temp->next can cause a crash if pos is invalid or list is short.

3. Final Answer:

   The loop does not check if temp is nullptr, causing possible crash. -> Option D

4. Quick Check:

   Always check temp != nullptr in traversal loops [OK]

Hint: Always check for nullptr when traversing [OK]

Common Mistakes:

• Ignoring nullptr checks in loops
• Not updating head for position 1 insert
• Incorrect order of pointer assignments

5. You have a doubly linked list: 5 <-> 10 <-> 15 <-> 20 <-> null. You want to insert a new node with value 12 at position 3. After insertion, what will be the correct sequence of the list? Also, explain how to handle insertion at the last position if the position is greater than the list length.

hard

A. 5 <-> 12 <-> 10 <-> 15 <-> 20 <-> null; Insert at last by replacing last node.

B. 5 <-> 10 <-> 15 <-> 12 <-> 20 <-> null; Insert at last by adding node before head.

C. 5 <-> 10 <-> 12 <-> 15 <-> 20 <-> null; Insert at last by traversing till last node and updating pointers.

D. 5 <-> 10 <-> 15 <-> 20 <-> 12 <-> null; Insert at last by ignoring position.

Solution

1. Step 1: Insert 12 at position 3

   Position 3 means after second node (10). Insert new node between 10 and 15, updating next and prev pointers accordingly.

2. Step 2: Handle insertion at last position if position > length

   Traverse to last node, then insert new node after it, updating last node's next and new node's prev pointers.

3. Final Answer:

   5 <-> 10 <-> 12 <-> 15 <-> 20 <-> null; Insert at last by traversing till last node and updating pointers. -> Option C

4. Quick Check:

   Insert at position 3 places node between 10 and 15; last insert by traversal [OK]

Hint: Insert at position or append if position too large [OK]

Common Mistakes:

• Inserting at wrong position
• Not updating prev pointer of next node
• Ignoring last position insertion logic