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 friend in the middle, you find the right spot, then the people hold hands with the new friend instead of directly with each other.

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: start at head node 1

head -> [curr->1] -> 2 -> 3 -> null

Why: We begin at the start to find the insertion point

Step 2: move curr to node 1 (position 1), stop before position 2

head -> [curr->1] -> 2 -> 3 -> null

Why: We stop at node before insertion position to link new node

Step 3: create new node with value 4 and link it after curr

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

Why: Insert new node by adjusting pointers

Result:

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

Annotated Code

DSA C#

using System;

public class Node
{
    public int data;
    public Node next;

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

public class LinkedList
{
    public Node head;

    public void InsertAtPosition(int data, int position)
    {
        Node newNode = new Node(data);

        if (position == 1)
        {
            newNode.next = head; // link new node to current head
            head = newNode; // new node becomes head
            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)
        {
            Console.WriteLine("Position out of bounds");
            return;
        }

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

    public void PrintList()
    {
        Node curr = head;
        while (curr != null)
        {
            Console.Write(curr.data);
            if (curr.next != null) Console.Write(" -> ");
            curr = curr.next;
        }
        Console.WriteLine(" -> null");
    }
}

class Program
{
    static void Main()
    {
        LinkedList list = new LinkedList();
        list.head = new Node(1);
        list.head.next = new Node(2);
        list.head.next.next = new Node(3);

        list.InsertAtPosition(4, 2);
        list.PrintList();
    }
}

if (position == 1) { newNode.next = head; // link new node to current head head = newNode; // new node becomes head return; }

handle insertion at the start by updating head pointer

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

move curr to node before insertion position

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

check if position is valid within list bounds

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

insert new node by adjusting pointers

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 which is O(1), inserting at middle requires traversal making it O(n)

Edge Cases

inserting at position 1 (start)

new node becomes the new head

DSA C#

if (position == 1)
        {
            newNode.next = head; // link new node to current head
            head = newNode; // new node becomes head
            return;
        }

inserting at position greater than list length + 1

prints 'Position out of bounds' and does not insert

DSA C#

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

inserting in an empty list at position 1

new node becomes head

DSA C#

if (position == 1)
        {
            newNode.next = head; // link new node to current head
            head = newNode; // new node becomes head
            return;
        }

When to Use This Pattern

When you need to add an element at a specific spot in a linked list, use the Insert at Middle Specific Position pattern to carefully link the new node without breaking the list.

Common Mistakes

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

Mistake: Not handling insertion at position 1 separately, causing head pointer errors
Fix: Add a special case to update head when inserting at position 1

Mistake: Not checking if position is out of bounds, leading to null pointer exceptions
Fix: Check if current node is null before insertion and handle invalid positions

Summary

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

Use when you want to add an element anywhere other than the start or end of 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 element only at the start of the list

B. Adding a new element exactly between two existing nodes at a given position

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

D. Removing an element from the middle of the list

Solution

1. Step 1: Understand linked list insertion

   Inserting at a specific position means placing a new node between existing nodes, not just at start or end.

2. Step 2: Define middle position insertion

   Middle insertion targets a position inside the list, not at boundaries.

3. Final Answer:

   Adding a new element exactly between two existing nodes at a given position -> Option B

4. Quick Check:

   Middle insertion = between nodes [OK]

Hint: Middle insertion means placing node between two nodes [OK]

Common Mistakes:

• Confusing middle insertion with adding at start
• Thinking middle insertion removes nodes
• Assuming insertion only happens at end

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

easy

A. Node current = head; for(int i=1; i<2; i++) current = current.next; newNode.next = current.next; current.next = newNode;

B. Node current = head; for(int i=1; i<3; i++) current = current.next; newNode.next = current.next; current.next = newNode;

C. Node current = head; for(int i=0; i<3; i++) current = current.next; newNode.next = current.next; current.next = newNode;

D. Node current = head; for(int i=1; i<=3; i++) current = current.next; newNode.next = current.next; current.next = newNode;

Solution

1. Step 1: Understand zero-based vs one-based indexing

   Position 3 means after 2 nodes, so loop runs i from 1 to 2 to reach node before position 3.

2. Step 2: Check loop and insertion logic

   Node current = head; for(int i=1; i<2; i++) current = current.next; newNode.next = current.next; current.next = newNode; loops correctly to node 2, then inserts newNode after it.

3. Final Answer:

   Node current = head; for(int i=1; i<2; i++) current = current.next; newNode.next = current.next; current.next = newNode; -> Option A

4. Quick Check:

   Loop to node before position = i < position-1 [OK]

Hint: Loop to node before position: i < position - 1 [OK]

Common Mistakes:

• Looping too many times and skipping target node
• Using wrong loop bounds causing null reference
• Not updating next pointers correctly

3. Given the linked list: 10 -> 20 -> 30 -> 40 -> null, what is the list after inserting 25 at position 3 using this code?

Node newNode = new Node(25);
Node current = head;
for(int i = 1; i < 2; i++) current = current.next;
newNode.next = current.next;
current.next = newNode;

medium

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

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

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

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

Solution

1. Step 1: Trace loop to position before insertion

   Loop runs i=1; i<2, so current moves from 10 to 20 (node at position 2).

2. Step 2: Insert newNode after current

   newNode.next points to current.next (30), current.next points to newNode (25).

3. Final Answer:

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

4. Quick Check:

   Inserted 25 at position 3 correctly [OK]

Hint: Insert after node at position-1 to place at position [OK]

Common Mistakes:

• Inserting at wrong position due to loop bounds
• Not updating newNode.next correctly
• Confusing node values and positions

4. What is the error in this code snippet that tries to insert a node at position 4 in a linked list?

Node current = head;
for(int i = 1; i <= 4; i++)
  current = current.next;
newNode.next = current.next;
current.next = newNode;

medium

A. Loop runs too many times causing current to be null before insertion

B. newNode.next is not assigned before insertion

C. The loop should start from i = 0 instead of 1

D. The newNode is not created before insertion

Solution

1. Step 1: Analyze loop bounds

   Loop runs i=1 to 4 inclusive, moving current 4 times ahead, which may make current null if list length is less than 5.

2. Step 2: Identify null reference risk

   Accessing current.next after current is null causes runtime error.

3. Final Answer:

   Loop runs too many times causing current to be null before insertion -> Option A

4. Quick Check:

   Loop bounds must stop at position-1 [OK]

Hint: Loop to position-1, not position, to avoid null [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Not checking for null before accessing next
• Incorrect loop start index

5. You have a singly linked list: 5 -> 15 -> 25 -> 35 -> 45 -> null. Write the steps to insert a new node with value 30 at position 4, and what will be the final list?

hard

A. Traverse to node at position 2, link new node's next to current's next, then set current's next to new node. Result: 5 -> 15 -> 30 -> 25 -> 35 -> 45 -> null

B. Traverse to node at position 4, link new node's next to current's next, then set current's next to new node. Result: 5 -> 15 -> 25 -> 35 -> 30 -> 45 -> null

C. Traverse to node at position 3, link new node's next to current's next, then set current's next to new node. Result: 5 -> 15 -> 25 -> 30 -> 35 -> 45 -> null

D. Insert new node at head and shift all nodes. Result: 30 -> 5 -> 15 -> 25 -> 35 -> 45 -> null

Solution

1. Step 1: Traverse to node before position 4

   Move current pointer to node at position 3 (value 25).

2. Step 2: Insert new node after current

   Set newNode.next to current.next (35), then current.next to newNode (30).

3. Final Answer:

   5 -> 15 -> 25 -> 30 -> 35 -> 45 -> null -> Option C

4. Quick Check:

   Insert at position 4 means after node 3 [OK]

Hint: Insert after node at position-1 for correct placement [OK]

Common Mistakes:

• Inserting at wrong position by off-by-one error
• Not updating next pointers correctly
• Confusing position with node value