Insert at Middle Specific Position in DSA C++

Mental Model

To insert a new item in the middle of a linked list, we find the spot by counting steps, then link the new item there without breaking the chain.

Analogy: Imagine a line of people holding hands. To add a new person in the middle, you find the right spot, then the new person holds hands with the neighbors, so the line stays connected.

Head -> 1 -> 2 -> 3 -> 4 -> null
                 ↑
             position 3

Dry Run Walkthrough

Input: list: 1 -> 2 -> 4 -> 5, insert value 3 at position 3

Goal: Insert the value 3 between nodes 2 and 4, so the list becomes 1 -> 2 -> 3 -> 4 -> 5

Step 1: start at head node 1

Head -> [curr->1] -> 2 -> 4 -> 5 -> null

Why: We begin traversal from the first node to find the insertion point

Step 2: move curr to node 2 (position 2)

Head -> 1 -> [curr->2] -> 4 -> 5 -> null

Why: We move forward to reach the node just before the insertion position

Step 3: create new node with value 3

newNode(3)

Why: Prepare the new node to insert into the list

Step 4: link new node's next to curr's next (node 4)

newNode(3) -> 4 -> 5 -> null

Why: New node points to the node currently at insertion position

Step 5: link curr's next to new node

Head -> 1 -> 2 -> [curr->3] -> 4 -> 5 -> null

Why: Insert new node after curr, maintaining list continuity

Result:

Head -> 1 -> 2 -> 3 -> 4 -> 5 -> null

Annotated Code

DSA C++

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

void insertAtPosition(Node*& head, int val, int pos) {
    if (pos == 1) { // insert at head
        Node* newNode = new Node(val);
        newNode->next = head;
        head = newNode;
        return;
    }
    Node* curr = head;
    int count = 1;
    while (curr != nullptr && count < pos - 1) {
        curr = curr->next; // advance curr to node before insertion
        count++;
    }
    if (curr == nullptr) {
        cout << "Position out of bounds" << endl;
        return;
    }
    Node* newNode = new Node(val); // create new node
    newNode->next = curr->next; // link new node to next node
    curr->next = newNode; // link previous node to new node
}

void printList(Node* head) {
    Node* curr = head;
    while (curr != nullptr) {
        cout << curr->data << " -> ";
        curr = curr->next;
    }
    cout << "null" << endl;
}

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(4);
    head->next->next->next = new Node(5);

    insertAtPosition(head, 3, 3);
    printList(head);
    return 0;
}

while (curr != nullptr && count < pos - 1) { curr = curr->next; // advance curr to node before insertion count++; }

advance curr to the node just before the insertion position

Node* newNode = new Node(val); // create new node newNode->next = curr->next; // link new node to next node curr->next = newNode; // link previous node to new node

insert new node by adjusting pointers to maintain list continuity

Output

1 -> 2 -> 3 -> 4 -> 5 -> null

Complexity Analysis

Time: O(n) because we may need to traverse up to n nodes to reach the insertion position

Space: O(1) because we only create one new node and use a few pointers

vs Alternative: Compared to inserting at head or tail which can be O(1), inserting in the middle requires traversal, making it O(n)

Edge Cases

inserting at position 1 (head)

new node becomes the new head

DSA C++

if (pos == 1) { ... }

inserting at position greater than list length + 1

prints 'Position out of bounds' and does not insert

DSA C++

if (curr == nullptr) { cout << "Position out of bounds" << endl; return; }

inserting into empty list at position 1

new node becomes the head

DSA C++

if (pos == 1) { ... }

When to Use This Pattern

When you need to add an element at a specific position in a linked list, use the insert at position pattern to carefully link the new node without breaking the chain.

Common Mistakes

Mistake: Not stopping traversal at the node before the insertion position
Fix: Traverse until position - 1 to insert correctly between nodes

Mistake: Not handling insertion at head separately
Fix: Add a condition to insert at head when position is 1

Mistake: Not checking if position is out of bounds
Fix: Check if curr is nullptr before insertion and handle gracefully

Summary

Inserts a new node at a given position in a singly linked list.

Use when you want to add an element anywhere except just at the start or end.

The key is to stop at the node before the insertion point and adjust pointers carefully.

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 insertion position

   Inserting at a specific middle position means placing the new node exactly at that position counting from the start (head) of the list.

2. Step 2: Differentiate from other insertions

   Insertion at start or end is different; here we insert in between nodes without replacing any node.

3. Final Answer:

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

4. Quick Check:

   Insert at position means place new node there [OK]

Hint: Insert means add new node at exact position, not replace [OK]

Common Mistakes:

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

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

easy

A. Node* temp = head; for(int i=1; i<2; i++) temp = temp->next; Node* newNode = new Node(10); newNode->next = temp->next; temp->next = newNode;

B. Node* newNode = new Node(10); newNode->next = head; head = newNode;

C. Node* temp = head; for(int i=1; i<3; i++) temp = temp->next; Node* newNode = new Node(10); newNode->next = temp->next; temp->next = newNode;

D. Node* newNode = new Node(10); head->next = newNode; newNode->next = NULL;

Solution

1. Step 1: Identify correct loop for position 3 insertion

   To insert at position 3, we stop at node 2 (position 2), so loop runs i=1 to i<2.

2. Step 2: Check pointer updates

   New node's next points to temp->next, then temp->next updated to new node. This correctly inserts at position 3.

3. Final Answer:

   Code snippet in option A correctly inserts at position 3 -> Option A

4. Quick Check:

   Loop stops at position before insertion [OK]

Hint: Loop till position-1, then insert new node [OK]

Common Mistakes:

• Looping one extra time causing wrong position
• Not updating newNode->next before temp->next
• Inserting at wrong position due to loop error

3. What will be the linked list after inserting value 15 at position 2 in the list: 5 -> 10 -> 20 -> null?

Node* head = new Node(5);
head->next = new Node(10);
head->next->next = new Node(20);

// Insert 15 at position 2
Node* temp = head;
for(int i=1; i<1; i++) temp = temp->next;
Node* newNode = new Node(15);
newNode->next = temp->next;
temp->next = newNode;

medium

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

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

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

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

Solution

1. Step 1: Trace loop to find insertion point

   Loop runs i=1 to i<1, so no iteration. temp points to head (value 5).

2. Step 2: Insert new node after temp

   New node 15 points to temp->next (10), then temp->next points to new node. List becomes 5 -> 15 -> 10 -> 20 -> null.

3. Final Answer:

   5 -> 15 -> 10 -> 20 -> null -> Option A

4. Quick Check:

   Insert after node 1 gives new node at position 2 [OK]

Hint: Loop zero times means insert after head [OK]

Common Mistakes:

• Miscounting loop iterations
• Inserting at wrong position
• Not updating pointers correctly

4. Identify the error in the following code that tries to insert a node with value 25 at position 4 in a linked list:

Node* temp = head;
for(int i=1; i<=4; i++) {
  temp = temp->next;
}
Node* newNode = new Node(25);
newNode->next = temp->next;
temp->next = newNode;

medium

A. No error, code works fine

B. New node's next pointer is not set correctly

C. New node is not created properly

D. Loop runs too many times causing temp to become NULL

Solution

1. Step 1: Analyze loop iterations

   Loop runs i=1 to i<=4 (4 times), moving temp 4 nodes ahead. For insertion at position 4, temp should stop at position 3.

2. Step 2: Consequence of loop error

   Temp moves too far, possibly NULL, causing runtime error when accessing temp->next.

3. Final Answer:

   Loop runs too many times causing temp to become NULL -> Option D

4. Quick Check:

   Loop must run position-2 times, not position times [OK]

Hint: Loop till position-2 to avoid NULL pointer [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Not checking for NULL before accessing next
• Incorrect loop range for insertion

5. Given a singly linked list with nodes: 1 -> 3 -> 5 -> 7 -> null, write the steps to insert a new node with value 4 at position 3. What will be the final list?

hard

A. 1 -> 4 -> 3 -> 5 -> 7 -> null

B. 4 -> 1 -> 3 -> 5 -> 7 -> null

C. 1 -> 3 -> 4 -> 5 -> 7 -> null

D. 1 -> 3 -> 5 -> 7 -> 4 -> null

Solution

1. Step 1: Traverse to node before position 3

   Start at head (1), move to next node (3) which is position 2. Stop here to insert after this node.

2. Step 2: Insert new node with value 4

   Create new node 4, set its next to current node's next (5), then update current node's next to new node.

3. Final Answer:

   1 -> 3 -> 4 -> 5 -> 7 -> null -> Option C

4. Quick Check:

   Insert at position 3 places new node between 3 and 5 [OK]

Hint: Stop at position-1 node, insert new node after it [OK]

Common Mistakes:

• Inserting at wrong position
• Not updating pointers correctly
• Confusing position counting from 0 or 1