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 data

↓

Check if position is 1

↓

Insert at head

↓

Traverse to position-1 node

↓

Adjust pointers: new node prev/next

↓

Adjust neighbors' pointers

↓

Done

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

Execution Sample

DSA C

void insertAtPosition(Node** head, int data, int pos) {
  Node* newNode = createNode(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 != NULL; i++) temp = temp->next;
  if (temp == NULL) return; // position out of bounds
  newNode->next = temp->next;
  if (temp->next) temp->next->prev = newNode;
  temp->next = newNode;
  newNode->prev = temp;
}

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

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Create new node with data=5	N/A	newNode created	10 <-> 20 <-> null
2	Check if position == 1	Head=Node(10)	No pointer change	10 <-> 20 <-> null
3	Traverse to position-1 (pos=3)	Start at head (10)	temp points to 10	10 <-> 20 <-> null
4	Traverse iteration 1	temp moves to 20	temp updated	10 <-> 20 <-> null
5	Adjust newNode pointers	temp=20	newNode->next = temp->next (null), newNode->prev = temp (20)	10 <-> 20 <-> null
6	Adjust neighbors' pointers	temp=20	temp->next = newNode, newNode->next->prev = newNode (no next node)	10 <-> 20 <-> 5 <-> null
7	Insertion complete	N/A	All pointers set	10 <-> 20 <-> 5 <-> null
8	Exit	N/A	Insertion done	10 <-> 20 <-> 5 <-> null

💡 Insertion done at position 3, traversal ended after reaching position-1 node.

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	Final
head	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)
temp	Node(10)	Node(10)	Node(20)	Node(20)	Node(20)
newNode	N/A	Node(5)	Node(5)	Node(5)	Node(5)

Key Moments - 3 Insights

Why do we stop traversal at position-1 instead of position?

We stop at position-1 (Step 3 and 4) because we need to insert the new node after this node. This allows us to adjust pointers correctly without losing the list structure.

What happens if the position is 1?

If position is 1 (Step 2), we insert the new node at the head by adjusting the head pointer and the previous head's prev pointer, as shown in the flow and code.

Why do we check if temp->next is NULL before adjusting its prev pointer?

Because if temp->next is NULL, it means we are inserting at the end. Trying to access temp->next->prev would cause an error. So we only update if temp->next exists (Step 6).

Visual Quiz - 3 Questions

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

A Node with data 20

B Node with data 5

C Node with data 10

D NULL

💡 Hint

Check the 'Current Node' column at Step 4 in the execution_table.

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

A Step 3

B Step 6

C Step 5

D Step 2

💡 Hint

Look at the 'Pointer Changes' column for Step 5 in the execution_table.

If position was 1, which step would handle the insertion?

A Step 4

B Step 2

C Step 5

D Step 6

💡 Hint

Step 2 checks if position == 1 in the execution_table.

Concept Snapshot

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

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 it at the head by adjusting the head pointer and the previous head's prev pointer. Otherwise, traverse the list to the node just before the desired position. Then, adjust the new node's next and prev pointers to link it between the nodes. Also, update the neighboring nodes' pointers to include the new node. This process ensures the list remains connected correctly. Edge cases like inserting at the end or empty list are handled by checking pointers before updating.

Practice

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

easy

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

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

C. The new node replaces the last node.

D. The list remains unchanged.

Solution

1. Step 1: Understand position 1 insertion

   Inserting at position 1 means adding the node at the start of the list.

2. Step 2: Effect on head pointer

   The new node becomes the head, and its next points to the old head.

3. Final Answer:

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

4. Quick Check:

   Position 1 insertion updates head [OK]

Hint: Position 1 means new head insertion [OK]

Common Mistakes:

• Thinking position 1 means end insertion
• Not updating the head pointer
• Ignoring previous pointer updates

2. Which of the following is the correct way to update pointers when inserting a node at position 3 in a doubly linked list?

easy

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

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

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

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

Solution

1. Step 1: Identify insertion point

   At position 3, newNode is inserted after temp (node at position 2).

2. Step 2: Update pointers correctly

   newNode's next points to temp's next, prev to temp; temp's next's prev updated to newNode; temp's next updated to newNode.

3. Final Answer:

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

4. Quick Check:

   Correct pointer updates for middle insertion [OK]

Hint: Update newNode next/prev before changing temp pointers [OK]

Common Mistakes:

• Swapping next and prev pointers
• Not updating temp->next->prev
• Forgetting to update temp->next

3. What will be the list after inserting a node with value 10 at position 2 in the doubly linked list: 5 <-> 15 <-> 20?

medium

A. 5 <-> 15 <-> 10 <-> 20

B. 10 <-> 5 <-> 15 <-> 20

C. 5 <-> 15 <-> 20 <-> 10

D. 5 <-> 10 <-> 15 <-> 20

Solution

1. Step 1: Locate position 2

   Position 2 means new node goes between nodes 1 (5) and 2 (15).

2. Step 2: Insert new node with value 10

   New node's prev points to 5, next points to 15; update 5's next and 15's prev accordingly.

3. Final Answer:

   5 <-> 10 <-> 15 <-> 20 -> Option D

4. Quick Check:

   Inserted node at position 2 between 5 and 15 [OK]

Hint: Position 2 means between first and second nodes [OK]

Common Mistakes:

• Inserting at wrong position
• Not updating both next and prev pointers
• Appending instead of inserting

4. Given the code snippet below, what is the error when inserting at position 4 in a list of 3 nodes?

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

medium

A. newNode is not allocated properly.

B. temp->next is NULL, so temp->next->prev causes a runtime error.

C. Loop runs one time too many causing segmentation fault.

D. prev pointer of newNode is not set.

Solution

1. Step 1: Analyze loop for position 4 in 3-node list

   Loop moves temp to node at position 3; temp->next is NULL (end of list).

2. Step 2: Check pointer updates

   Accessing temp->next->prev causes runtime error because temp->next is NULL.

3. Final Answer:

   temp->next is NULL, so temp->next->prev causes a runtime error. -> Option B

4. Quick Check:

   Accessing NULL pointer causes runtime error [OK]

Hint: Check for NULL before accessing next->prev [OK]

Common Mistakes:

• Not checking if temp->next is NULL
• Assuming list is longer than it is
• Ignoring edge case at list end

5. You have a doubly linked list: 1 <-> 3 <-> 5 <-> 7. You want to insert a node with value 4 at position 3. After insertion, what will be the correct list and how do you handle the pointers to maintain list integrity?

hard

A. 1 <-> 3 <-> 4 <-> 5 <-> 7; Set newNode->prev = node at pos 2, newNode->next = node at pos 3, update adjacent nodes' pointers.

B. 1 <-> 3 <-> 5 <-> 4 <-> 7; Insert newNode after node at pos 3 without updating prev pointers.

C. 1 <-> 4 <-> 3 <-> 5 <-> 7; Insert newNode at head and shift others.

D. 1 <-> 3 <-> 5 <-> 7 <-> 4; Append newNode at end regardless of position.

Solution

1. Step 1: Identify insertion position and nodes

   Position 3 means new node goes between nodes with values 3 (pos 2) and 5 (pos 3).

2. Step 2: Update pointers to insert new node

   Set newNode->prev to node with value 3, newNode->next to node with value 5; update node 3's next and node 5's prev to newNode.

3. Step 3: Verify list integrity

   After insertion, list is 1 <-> 3 <-> 4 <-> 5 <-> 7 with all pointers correctly linked.

4. Final Answer:

   1 <-> 3 <-> 4 <-> 5 <-> 7; Set newNode->prev = node at pos 2, newNode->next = node at pos 3, update adjacent nodes' pointers. -> Option A

5. Quick Check:

   Proper pointer updates maintain doubly linked list [OK]

Hint: Insert between nodes, update both next and prev pointers [OK]

Common Mistakes:

• Inserting at wrong position
• Not updating both adjacent nodes' pointers
• Breaking list links causing traversal errors