Insert at Middle Specific Position in DSA Python

Mental Model

To insert a new item in the middle of a linked list, we find the spot by moving step-by-step, then link the new item in without breaking the chain.

Analogy: Imagine a train with connected cars. To add a new car in the middle, you uncouple the train at the right spot, insert the new car, then reconnect the rest.

head -> 1 -> 2 -> 3 -> 4 -> null
                 ↑ insert here

Dry Run Walkthrough

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

Goal: Insert the value 5 as the third element in the list

Step 1: start at head node (value 1)

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

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

Step 2: move curr to next node (value 2)

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

Why: Advance to node before insertion position (position 2)

Step 3: create new node with value 5

new_node(5)

Why: Prepare the new node to insert

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

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

Why: Connect new node to the rest of the list after insertion point

Step 5: link curr's next to new node

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

Why: Insert new node into the list by updating previous node's next

Result:

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

Annotated Code

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insert_at_position(self, val, pos):
        new_node = Node(val)  # create new node
        if pos == 1:  # insert at head
            new_node.next = self.head
            self.head = new_node
            return
        curr = self.head
        count = 1
        while curr is not None and count < pos - 1:
            curr = curr.next  # move curr to node before insertion
            count += 1
        if curr is None:
            return  # position out of bounds, do nothing
        new_node.next = curr.next  # link new node to next node
        curr.next = new_node  # link previous node to new node

    def __str__(self):
        result = []
        curr = self.head
        while curr:
            result.append(str(curr.val))
            curr = curr.next
        return ' -> '.join(result) + ' -> null'

# Driver code
ll = LinkedList()
ll.head = Node(1)
ll.head.next = Node(2)
ll.head.next.next = Node(3)
ll.head.next.next.next = Node(4)

ll.insert_at_position(5, 3)
print(ll)

new_node = Node(val) # create new node

prepare the new node to insert

if pos == 1: # insert at head

handle insertion at the start of the list

while curr is not None and count < pos - 1:

move curr to node before insertion position

new_node.next = curr.next # link new node to next node

connect new node to the rest of the list

curr.next = new_node # link previous node to new node

insert new node by updating previous node's next

Output

1 -> 2 -> 5 -> 3 -> 4 -> 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 is O(1), inserting in the middle requires traversal making it O(n)

Edge Cases

insert at position 1 (head)

new node becomes the new head

DSA Python

if pos == 1:  # insert at head

insert at position greater than list length

no insertion happens, list remains unchanged

DSA Python

if curr is None:
            return  # position out of bounds, do nothing

insert into empty list at position 1

new node becomes the head

DSA Python

if pos == 1:  # insert at head

When to Use This Pattern

When you need to add an element at a specific spot inside 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 correctly link the new node

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 current node is None before insertion and skip if so

Summary

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

Use it 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 link the new node in without breaking the list.