Insert at Middle Specific Position in DSA C - Execution Trace

Concept Flow - Insert at Middle Specific Position

Start

↓

Check if list is empty

↓

Create new node

↓

Insert new node

↓

Update links

↓

End

Start by checking if the list is empty. If yes, create the new node as head. Otherwise, traverse to the node before the desired position, insert the new node, and update links.

Execution Sample

DSA C

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

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

Execution Table

Step	pos	temp position	Action	List state after step
1	3	head (pos 1)	Create new node with data=99	1 -> 2 -> 3 -> 4 -> null
2	3	pos 1	Traverse to node before position 3 (pos 2)	1 -> 2 -> 3 -> 4 -> null
3	3	pos 2	Insert new node after pos 2	1 -> 2 -> 99 -> 3 -> 4 -> null
4	3	pos 2	Update links	1 -> 2 -> 99 -> 3 -> 4 -> null
5	3	pos 2	End	1 -> 2 -> 99 -> 3 -> 4 -> null

💡 Insertion complete at position 3, list updated successfully.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
pos	3	3	3	3	3
temp	head (pos 1)	head (pos 1)	pos 2	pos 2	pos 2
newNode->data	N/A	99	99	99	99
newNode->next	N/A	NULL	NULL	pos 3	pos 3

Key Moments - 3 Insights

Why do we traverse to position-1 instead of the exact position?

Because we need to update the 'next' pointer of the node before the insertion point to point to the new node. See execution_table step 2 where temp stops at position 2 before inserting at position 3.

What happens if the position is 1?

The new node becomes the new head. Its 'next' points to the old head. This is handled separately in the code before traversal, not shown in this trace.

What if the position is beyond the list length?

The traversal will reach NULL before position-1, so insertion is skipped. This prevents invalid memory access.

Visual Quiz - 3 Questions

Look at the execution_table, what is the list state after step 3?

A 99 -> 1 -> 2 -> 3 -> 4 -> null

B 1 -> 2 -> 3 -> 4 -> null

C 1 -> 2 -> 99 -> 3 -> 4 -> null

D 1 -> 99 -> 2 -> 3 -> 4 -> null

💡 Hint

Check the 'List state after step' column in execution_table row 3.

At which step does the temp pointer move from position 1 to position 2?

A Step 2

B Step 1

C Step 3

D Step 4

💡 Hint

Look at the 'temp position' column in execution_table rows 1 and 2.

If pos was 1, what would be the new head's data after insertion?

A Data of old head

B 99

C NULL

D Data of node at position 2

💡 Hint

Recall key_moments answer about insertion at position 1 making new node the head.

Concept Snapshot

Insert at Middle Specific Position in singly linked list:
- Create new node with data
- If position is 1, new node points to head, becomes new head
- Else, traverse to node before position
- Insert new node by adjusting next pointers
- Handles invalid positions by skipping insertion

Full Transcript

This visual trace shows how to insert a new node at a specific middle position in a singly linked list. We start by creating the new node with the given data. If the position is 1, the new node becomes the head. Otherwise, we traverse the list to the node just before the desired position. Then we insert the new node by updating the next pointers to link it in. The execution table tracks each step, showing the position, traversal, and list state. The variable tracker shows how variables like temp and newNode change. Key moments clarify why we stop traversal at position-1 and how edge cases like position 1 or invalid positions are handled. The quiz tests understanding of list state after insertion and pointer movement. This method ensures safe and correct insertion at any valid middle position.

Practice

1. What does inserting a node at a specific middle position in a linked list mean?

easy

A. Adding a new node only at the start of the list

B. Adding a new node exactly at the given position counting from the head

C. Adding a new node only at the end of the list

D. Replacing the node at the given position with a new node

Solution

1. Step 1: Understand the position concept

   Inserting at a specific position means counting nodes from the head and placing the new node exactly there.

2. Step 2: Differentiate from other insertions

   Insertion at start or end is special cases; here we insert in the middle without removing nodes.

3. Final Answer:

   Adding a new node exactly at the given position counting from the head -> Option B

4. Quick Check:

   Insert at position = Insert node at that place [OK]

Hint: Insert at position means count nodes and place new node there [OK]

Common Mistakes:

• Confusing insertion with replacement
• Thinking insertion only happens at start or end
• Ignoring the position count from head

2. Which of the following C code snippets correctly inserts a new node at position 3 in a singly linked list?

easy

A. Traverse to node 2, set newNode->next = current->next; current->next = newNode;

B. Set newNode->next = head; head = newNode;

C. Traverse to node 3, set current->next = newNode; newNode->next = NULL;

D. Set newNode->next = NULL; current->next = newNode;

Solution

1. Step 1: Identify correct traversal

   To insert at position 3, we must reach node 2 (one before position 3).

2. Step 2: Link new node correctly

   Set newNode->next to current->next, then current->next to newNode to insert properly.

3. Final Answer:

   Traverse to node 2, set newNode->next = current->next; current->next = newNode; -> Option A

4. Quick Check:

   Insert at pos 3 = link after node 2 [OK]

Hint: Insert after (position-1)th node by adjusting pointers [OK]

Common Mistakes:

• Inserting at wrong node position
• Not updating newNode->next before linking
• Setting newNode->next to NULL incorrectly

3. What will be the linked list after inserting a node with value 99 at position 3 in the list 10 -> 20 -> 30 -> 40 -> NULL?

medium

A. 99 -> 10 -> 20 -> 30 -> 40 -> NULL

B. 10 -> 20 -> 30 -> 99 -> 40 -> NULL

C. 10 -> 20 -> 30 -> 40 -> 99 -> NULL

D. 10 -> 20 -> 99 -> 30 -> 40 -> NULL

Solution

1. Step 1: Identify position 3 in the list

   Positions: 1=10, 2=20, 3=30, so new node goes before 30.

2. Step 2: Insert new node at position 3

   New node with 99 points to 30, node 20 points to new node.

3. Final Answer:

   10 -> 20 -> 99 -> 30 -> 40 -> NULL -> Option D

4. Quick Check:

   Insert at pos 3 places 99 before 30 [OK]

Hint: Insert at pos 3 means new node is third in list [OK]

Common Mistakes:

• Inserting after instead of at position
• Appending at end instead of middle
• Confusing node values and positions

4. Given the following code snippet to insert at position 2, what is the error?

void insertAtPos(Node** head, int data, int pos) {
  Node* newNode = malloc(sizeof(Node));
  newNode->data = data;
  newNode->next = NULL;
  Node* temp = *head;
  for(int i = 1; i < pos - 1; i++) {
    temp = temp->next;
  }
  newNode->next = temp->next;
  temp->next = newNode;
}

medium

A. Memory for newNode is not allocated

B. newNode->next is not set before linking

C. Loop runs one time too many causing temp to be NULL

D. Head pointer is not updated after insertion

Solution

1. Step 1: Analyze loop for position 2

   Loop should run from i=1 to i < pos-1 to stop at node before insertion point.

2. Step 2: Check temp usage after loop

   Original loop runs one time too many, moving temp to node 2 instead of node 1, causing incorrect insertion or NULL access.

3. Final Answer:

   Loop runs one time too many causing temp to be NULL -> Option C

4. Quick Check:

   Loop overshoots node before position [OK]

Hint: Loop should stop at position-1 to avoid NULL [OK]

Common Mistakes:

• Loop runs to pos instead of pos-1
• Not checking for NULL before accessing temp->next
• Forgetting to allocate memory for new node

5. You have a singly linked list with 5 nodes: 1 -> 2 -> 3 -> 4 -> 5 -> NULL. You want to insert a node with value 99 at position 6. What should happen and what will be the final list?

hard

A. Node 99 is appended at the end; list becomes 1 -> 2 -> 3 -> 4 -> 5 -> 99 -> NULL

B. Node 99 is inserted at position 5; list becomes 1 -> 2 -> 3 -> 4 -> 99 -> 5 -> NULL

C. Node 99 replaces node 5; list becomes 1 -> 2 -> 3 -> 4 -> 99 -> NULL

D. Insertion fails because position 6 is invalid; list remains unchanged

Solution

1. Step 1: Check list length and position

   List has 5 nodes; position 6 means insert after last node (append).

2. Step 2: Insert node at end

   Since position is one more than length, node 99 is added after node 5.

3. Final Answer:

   Node 99 is appended at the end; list becomes 1 -> 2 -> 3 -> 4 -> 5 -> 99 -> NULL -> Option A

4. Quick Check:

   Insert at pos > length means append [OK]

Hint: Position beyond length means append at end [OK]

Common Mistakes:

• Rejecting valid append position
• Replacing last node instead of appending
• Inserting at wrong position due to off-by-one