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.

Practice

1. What does it mean to insert an element at a specific middle position in a list?

easy

A. Add the element exactly at the given index, shifting others right

B. Replace the element at the given index with the new element

C. Add the element only if the list is empty

D. Add the element at the end of the list regardless of position

Solution

1. Step 1: Understand list insertion

   Inserting at a specific position means placing the new element at that index and moving existing elements to the right.

2. Step 2: Differentiate from replacement

   Replacing overwrites the element, but insertion shifts elements to keep all.

3. Final Answer:

   Add the element exactly at the given index, shifting others right -> Option A

4. Quick Check:

   Insert means add and shift, not replace or append [OK]

Hint: Insert shifts elements right at the given index [OK]

Common Mistakes:

• Confusing insert with replace
• Thinking insert always adds at end
• Assuming insert only works on empty lists

2. Which of the following is the correct syntax to insert the value 10 at index 2 in a Python list named lst?

easy

A. lst.append(2, 10)

B. lst.insert(2, 10)

C. lst.add(2, 10)

D. lst[2] = 10

Solution

1. Step 1: Recall Python list insertion method

   Python lists use the insert(index, value) method to add an element at a specific position.

2. Step 2: Check other options

   add is not a list method, append adds only at the end, and lst[2] = 10 replaces the element at index 2.

3. Final Answer:

   lst.insert(2, 10) -> Option B

4. Quick Check:

   Use insert(index, value) to add at position [OK]

Hint: Use insert(index, value) to add at any position [OK]

Common Mistakes:

• Using append to insert in middle
• Trying to assign with lst[2] = 10 instead of insert
• Using non-existent add method

3. What will be the output of the following code?

lst = [1, 2, 4, 5]
lst.insert(2, 3)
print(lst)

medium

A. [1, 2, 3, 4, 5]

B. [1, 2, 4, 3, 5]

C. [3, 1, 2, 4, 5]

D. [1, 2, 4, 5, 3]

Solution

1. Step 1: Understand insert at index 2

   Index 2 means the third position (0-based). Inserting 3 here shifts 4 and 5 right.

2. Step 2: Visualize the list after insertion

   List becomes [1, 2, 3, 4, 5] after insertion.

3. Final Answer:

   [1, 2, 3, 4, 5] -> Option A

4. Quick Check:

   Insert at index 2 places 3 before 4 [OK]

Hint: Index 2 means third position, insert shifts right [OK]

Common Mistakes:

• Inserting after index instead of at index
• Confusing insert with replace
• Miscounting zero-based index

4. Find the error in the following code that tries to insert 99 at index 3:

lst = [10, 20, 30]
lst.insert(4, 99)
print(lst)

medium

A. Index 4 is out of range, causes error

B. insert method requires two arguments

C. No error; 99 is added at the end

D. lst should be converted to a set before insert

Solution

1. Step 1: Check index validity for insert

   Python's insert allows index beyond list length; it adds element at the end.

2. Step 2: Confirm behavior of insert with large index

   Since index 4 > length 3, 99 is appended at the end without error.

3. Final Answer:

   No error; 99 is added at the end -> Option C

4. Quick Check:

   Insert with large index appends at end [OK]

Hint: Insert with index > length appends at end [OK]

Common Mistakes:

• Assuming index out of range causes error
• Confusing insert with assignment
• Thinking list must be converted to set

5. Given a list lst = [5, 10, 15, 20, 25], write code to insert the value 12 exactly in the middle of the list. What will be the list after insertion?

hard

A. [5, 10, 15, 12, 20, 25]

B. [12, 5, 10, 15, 20, 25]

C. [5, 12, 10, 15, 20, 25]

D. [5, 10, 12, 15, 20, 25]

Solution

1. Step 1: Calculate middle index of the list

   List length is 5, middle index is length // 2 = 2.

2. Step 2: Insert 12 at index 2

   Using lst.insert(2, 12) places 12 between 10 and 15.

3. Final Answer:

   [5, 10, 12, 15, 20, 25] -> Option D

4. Quick Check:

   Middle index = 2, insert shifts elements right [OK]

Hint: Middle index = length // 2, insert there [OK]

Common Mistakes:

• Inserting at wrong index (like 3)
• Replacing element instead of inserting
• Not calculating middle index correctly