Insert at Middle Specific Position in DSA C

Mental Model

We add a new item exactly where we want in the list by moving step-by-step to that spot and linking the new item there.

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 next person, and the previous person holds hands with the new person.

head -> 1 -> 2 -> 3 -> null
          ↑
       position 2

Dry Run Walkthrough

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

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

Step 1: create new node with value 4

head -> 1 -> 2 -> 3 -> null
new_node: 4 -> null

Why: We need a new node ready to insert

Step 2: start at head node 1, move to position 1 (one step before position 2)

head -> [curr->1] -> 2 -> 3 -> null
new_node: 4 -> null

Why: We stop before the insertion point to link new node

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

head -> [curr->1] -> 2 -> 3 -> null
new_node: 4 -> 2 -> 3 -> null

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

Step 4: link curr's next to new node

head -> 1 -> [new_node->4] -> 2 -> 3 -> null

Why: Previous node now points to new node, completing insertion

Result:

head -> 1 -> 4 -> 2 -> 3 -> null

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Define node structure
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Insert at specific position (1-based index)
void insertAtPosition(Node** head, int data, int position) {
    Node* newNode = createNode(data); // create new node

    if (position == 1) { // insert at head
        newNode->next = *head; // new node points to current head
        *head = newNode; // head updated to new node
        return;
    }

    Node* curr = *head;
    int count = 1;
    // move curr to node before insertion point
    while (curr != NULL && count < position - 1) {
        curr = curr->next; // advance curr
        count++;
    }

    if (curr == NULL) { // position is beyond list length
        free(newNode); // avoid memory leak
        return; // do nothing
    }

    newNode->next = curr->next; // new node points to next node
    curr->next = newNode; // previous node points to new node
}

// Print list
void printList(Node* head) {
    Node* curr = head;
    while (curr != NULL) {
        printf("%d -> ", curr->data);
        curr = curr->next;
    }
    printf("null\n");
}

int main() {
    // Create initial list: 1 -> 2 -> 3 -> null
    Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);

    // Insert 4 at position 2
    insertAtPosition(&head, 4, 2);

    // Print final list
    printList(head);

    return 0;
}

Node* newNode = createNode(data);

create new node to insert

if (position == 1) { newNode->next = *head; *head = newNode; return; }

handle insertion at head

while (curr != NULL && count < position - 1) { curr = curr->next; count++; }

move curr to node before insertion point

if (curr == NULL) { free(newNode); return; }

handle position beyond list length

newNode->next = curr->next; curr->next = newNode;

link new node into list

Output

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

Complexity Analysis

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

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, so it is slower but necessary for precise placement

Edge Cases

insert at position 1 (head insertion)

new node becomes the new head

DSA C

if (position == 1) { newNode->next = *head; *head = newNode; return; }

insert at position beyond list length

no insertion happens, new node is freed

DSA C

if (curr == NULL) { free(newNode); return; }

insert into empty list at position 1

new node becomes the head

DSA C

if (position == 1) { newNode->next = *head; *head = newNode; return; }

When to Use This Pattern

When you need to add an item exactly at a certain spot in a list, use the insert at position pattern to carefully link the new node in place.

Common Mistakes

Mistake: Not stopping at the node before the insertion position, causing incorrect links
Fix: Traverse until position - 1 to correctly link the new node

Mistake: Not handling insertion at head separately, leading to lost head pointer
Fix: Check if position is 1 and update head pointer accordingly

Mistake: Not checking if position is beyond list length, causing null pointer errors
Fix: Check if current node is NULL before insertion and handle gracefully

Summary

It inserts a new node at a given position inside a linked list.

Use it when you want to add an element not just at the start or end, but somewhere in the middle.

The key is to stop at the node before the insertion point and link the new node between nodes.

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