Insert at Middle Specific Position in DSA Java

Mental Model

To add a new item in the middle of a list, find the right spot and link the new item there without breaking the chain.

Analogy: Imagine a train of connected cars. To add a new car in the middle, you disconnect the link between two cars, insert the new car, then reconnect the links so the train stays connected.

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

Dry Run Walkthrough

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

Goal: Insert the value 3 at the 3rd position so the list becomes 1 -> 2 -> 3 -> 4 -> 5 -> null

Step 1: start at head node (value 1), prepare to move to position 2

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

Why: We need to reach the node just before the insertion point

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

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

Why: We stop at position 2 to insert after it

Step 3: create new node with value 3, link it to curr's next (node 4)

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

Why: New node must point to the next node to keep chain intact

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

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

Why: Curr now points to new node, completing insertion

Result:

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

Annotated Code

DSA Java

class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class LinkedList {
    Node head;

    public void insertAtPosition(int data, int position) {
        Node newNode = new Node(data);
        if (position == 1) {
            newNode.next = head;
            head = newNode;
            return;
        }
        Node curr = head;
        int count = 1;
        while (curr != null && count < position - 1) {
            curr = curr.next; // advance curr to node before insertion point
            count++;
        }
        if (curr == null) {
            System.out.println("Position out of bounds");
            return;
        }
        newNode.next = curr.next; // link new node to next node
        curr.next = newNode; // link curr to new node
    }

    public void printList() {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data + " -> ");
            curr = curr.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.head = new Node(1);
        list.head.next = new Node(2);
        list.head.next.next = new Node(4);
        list.head.next.next.next = new Node(5);

        list.insertAtPosition(3, 3);
        list.printList();
    }
}

while (curr != null && count < position - 1) { curr = curr.next; // advance curr to node before insertion point count++; }

advance curr to node before insertion position to prepare insertion

newNode.next = curr.next; // link new node to next node

link new node to the node currently after curr to keep chain

curr.next = newNode; // link curr to new node

link curr to new node to insert it in the list

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

Edge Cases

inserting at position 1 (head)

new node becomes the new head

DSA Java

if (position == 1) {
    newNode.next = head;
    head = newNode;
    return;
}

inserting at position greater than list length + 1

prints 'Position out of bounds' and does not insert

DSA Java

if (curr == null) {
    System.out.println("Position out of bounds");
    return;
}

inserting in an empty list at position 1

new node becomes head

DSA Java

if (position == 1) {
    newNode.next = head;
    head = newNode;
    return;
}

When to Use This Pattern

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

Common Mistakes

Mistake: Not stopping traversal at the node before the insertion point, causing incorrect links
Fix: Traverse until position - 1 node before inserting to maintain correct links

Mistake: Not handling insertion at head (position 1) separately
Fix: Add a condition to insert at head by updating head pointer

Mistake: Not checking if position is out of bounds, leading to null pointer errors
Fix: Check if curr is null after traversal and handle out of bounds gracefully

Summary

Inserts a new node at a given position in a linked list by adjusting pointers.

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

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

Practice

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

easy

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

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

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

   Inserting at a specific position means placing the new node exactly at that index, shifting others if needed.

2. Step 2: Differentiate from other insertions

   Start or end insertions are special cases, but middle insertion targets a specific index inside the list.

3. Final Answer:

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

4. Quick Check:

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

Hint: Middle insert means place node exactly at given index [OK]

Common Mistakes:

• Confusing insertion with replacement
• Thinking insertion only happens at start or end
• Ignoring zero-based or one-based indexing

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

easy

A. Node newNode = new Node(10); newNode.next = head.next.next.next; head.next.next.next = newNode;

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

C. Node newNode = new Node(10); newNode.next = head.next.next; head.next.next = newNode;

D. Node newNode = new Node(10); newNode.next = head; head = newNode;

Solution

1. Step 1: Identify position 3 in zero-based indexing

   Position 3 means after two nodes: head -> next -> next, so newNode.next should point to head.next.next.

2. Step 2: Link newNode correctly

   Set newNode.next to head.next.next, then update head.next.next to newNode to insert at position 3.

3. Final Answer:

   Node newNode = new Node(10); newNode.next = head.next.next; head.next.next = newNode; -> Option C

4. Quick Check:

   Insert at position 3 = link newNode after second node [OK]

Hint: Link new node's next to current node at position, then update previous node [OK]

Common Mistakes:

• Incorrectly setting newNode.next to wrong node
• Not updating previous node's next pointer
• Confusing position indexing

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

Node head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
head.next.next.next = new Node(40);

// Insert 25 at position 2
Node newNode = new Node(25);
Node temp = head;
for (int i = 1; i < 2; i++) {
    temp = temp.next;
}
newNode.next = temp.next;
temp.next = newNode;

medium

A. 25 -> 10 -> 20 -> 30 -> 40 -> null

B. 10 -> 20 -> 30 -> 25 -> 40 -> null

C. 10 -> 20 -> 25 -> 30 -> 40 -> null

D. 10 -> 25 -> 20 -> 30 -> 40 -> null

Solution

1. Step 1: Traverse to node at position 1

   The loop runs once (i=1), so temp points to node with value 20.

2. Step 2: Insert newNode after temp

   newNode.next points to temp.next (node 30), then temp.next points to newNode, inserting 25 after 20.

3. Final Answer:

   10 -> 20 -> 30 -> 25 -> 40 -> null -> Option B

4. Quick Check:

   Insert at position 2 places 25 after 20 [OK]

Hint: Loop to node before position, link new node next, update previous next [OK]

Common Mistakes:

• Looping one extra time causing wrong insertion
• Not updating newNode.next correctly
• Confusing position indexing

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

Node newNode = new Node(15);
Node temp = head;
for (int i = 0; i < 1; i++) {
    temp = temp.next;
}
newNode.next = temp.next;
temp.next = newNode;

medium

A. Loop moves temp too far, skipping the head node

B. newNode.next is assigned incorrectly

C. temp.next is not updated after insertion

D. No error, code works fine

Solution

1. Step 1: Analyze loop movement

   The loop runs once, moving temp from head to head.next, so temp points to node at position 1, not before it.

2. Step 2: Understand insertion point

   To insert at position 1, temp should point to node before position 1 (head), but here it points to position 1 node, causing incorrect insertion.

3. Final Answer:

   Loop moves temp too far, skipping the head node -> Option A

4. Quick Check:

   Loop should stop before position to insert [OK]

Hint: Loop to node before position, not at position [OK]

Common Mistakes:

• Looping one time too many
• Confusing position indexing
• Not handling insertion at position 0 separately

5. Given a singly linked list with nodes: 5 -> 10 -> 15 -> 20 -> null, write the output after inserting a node with value 12 at position 3 using the following code:

Node newNode = new Node(12);
Node temp = head;
int position = 3;
for (int i = 1; i < position - 1; i++) {
    temp = temp.next;
}
newNode.next = temp.next;
temp.next = newNode;

// Print list
Node current = head;
while (current != null) {
    System.out.print(current.data + " -> ");
    current = current.next;
}
System.out.print("null");

hard

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

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

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

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

Solution

1. Step 1: Loop to node before position 3

   The loop runs with i=1 only, so temp moves from head (5) to next (10), which is node before position 3.

2. Step 2: Insert newNode after temp

   newNode.next points to temp.next (15), then temp.next points to newNode, inserting 12 between 10 and 15.

3. Final Answer:

   5 -> 10 -> 12 -> 15 -> 20 -> null -> Option D

4. Quick Check:

   Insert at position 3 places 12 after 10 [OK]

Hint: Loop to node before position, link new node, update next pointers [OK]

Common Mistakes:

• Looping too many times causing wrong insertion
• Not updating newNode.next correctly
• Confusing position indexing