Insert at Specific Position in Doubly Linked List in DSA Python

Mental Model

A doubly linked list lets you move forward and backward through nodes. To insert at a position, you find that spot and link the new node between neighbors.

Analogy: Imagine a train with cars connected front and back. To add a new car in the middle, you disconnect the two cars at that spot and connect the new car between them.

null ← 1 ↔ 2 ↔ 3 -> null
Positions:    1    2    3

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3, insert value 4 at position 2

Goal: Insert the value 4 between nodes 1 and 2, making it the new second node

Step 1: Create new node with value 4

null ← 1 ↔ 2 ↔ 3 -> null, new_node=4 (isolated)

Why: We need a new node ready to insert

Step 2: Traverse to node at position 1 (value 1)

null ← [1] ↔ 2 ↔ 3 -> null, new_node=4

Why: We find the node after which we insert

Step 3: Set new_node's next to node 2 and prev to node 1

null ← 1 ↔ [4] ↔ 2 ↔ 3 -> null

Why: Link new node to neighbors

Step 4: Update node 1's next to new_node and node 2's prev to new_node

null ← 1 ↔ 4 ↔ 2 ↔ 3 -> null

Why: Complete the links so list stays connected

Result:

null ← 1 ↔ 4 ↔ 2 ↔ 3 -> null

Annotated Code

DSA Python

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

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

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = new_node
        new_node.prev = curr

    def insert_at_position(self, data, position):
        new_node = Node(data)  # create new node
        if position == 1:  # insert at head
            new_node.next = self.head
            if self.head:
                self.head.prev = new_node
            self.head = new_node
            return
        curr = self.head
        count = 1
        while curr and count < position - 1:
            curr = curr.next  # move to node before position
            count += 1
        if not curr:  # position is beyond list length
            return
        new_node.next = curr.next  # link new_node next
        if curr.next:
            curr.next.prev = new_node  # link next node prev
        curr.next = new_node  # link current node next
        new_node.prev = curr  # link new_node prev

    def __str__(self):
        values = []
        curr = self.head
        while curr:
            values.append(str(curr.data))
            curr = curr.next
        return ' ↔ '.join(values)

# Driver code
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.insert_at_position(4, 2)
print(dll)

new_node = Node(data) # create new node

prepare new node to insert

if position == 1: # insert at head

handle insertion at start of list

while curr and count < position - 1: curr = curr.next # move to node before position count += 1

traverse to node before insertion point

new_node.next = curr.next # link new_node next

connect new node's next pointer

if curr.next: curr.next.prev = new_node # link next node prev

connect next node's prev pointer if exists

curr.next = new_node # link current node next

connect current node's next pointer

new_node.prev = curr # link new_node prev

connect new node's prev pointer

Output

1 ↔ 4 ↔ 2 ↔ 3

Complexity Analysis

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

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 at a specific position requires traversal, making it O(n)

Edge Cases

Insert at position 1 (head insertion)

New node becomes the new head, previous head's prev updated

DSA Python

if position == 1:  # insert at head

Insert at position beyond list length

No insertion happens, list remains unchanged

DSA Python

if not curr:  # position is beyond list length

Insert into empty list at position 1

New node becomes the head

DSA Python

if position == 1:  # insert at head

When to Use This Pattern

When a problem asks to insert an element at a specific position in a doubly linked list, use traversal to find the spot and update four pointers to insert the node.

Common Mistakes

Mistake: Not updating the prev pointer of the node after the inserted node
Fix: Always update curr.next.prev = new_node if curr.next exists

Mistake: Not handling insertion at the head separately
Fix: Add a special case for position 1 to update head and pointers correctly

Summary

Inserts a new node at a given position in a doubly linked list by adjusting next and prev pointers.

Use when you need to add an element anywhere in the list, not just at the ends.

The key is to link the new node between its neighbors by updating four pointers carefully.

Practice

1. What is the main purpose of inserting a node at a specific position in a doubly linked list?

easy

A. To add a new node exactly where you want in the list

B. To delete a node from the list

C. To reverse the entire list

D. To find the length of the list

Solution

1. Step 1: Understand insertion in doubly linked list

   Insertion at a specific position means adding a new node exactly at that place, shifting others if needed.

2. Step 2: Differentiate from other operations

   Deleting removes nodes, reversing changes order, and length counts nodes, none insert at a position.

3. Final Answer:

   To add a new node exactly where you want in the list -> Option A

4. Quick Check:

   Insert at position = Add node at exact place [OK]

Hint: Insertion means adding, not deleting or reversing [OK]

Common Mistakes:

• Confusing insertion with deletion
• Thinking insertion changes list order
• Mixing insertion with counting nodes

2. Which of the following is the correct way to update the previous pointer of the new node when inserting at position 3 in a doubly linked list?

easy

A. new_node.prev = null

B. new_node.prev = head

C. new_node.prev = head.next.next

D. new_node.prev = head.next

Solution

1. Step 1: Identify the node before position 3

   Position 3 means the new node comes after the second node, so prev points to node at position 2 (head.next).

2. Step 2: Assign previous pointer correctly

   new_node.prev must point to the node at position 2, which is head.next.

3. Final Answer:

   new_node.prev = head.next -> Option D

4. Quick Check:

   Prev pointer = node before insertion [OK]

Hint: Prev points to node before insertion position [OK]

Common Mistakes:

• Setting prev to null instead of correct node
• Confusing prev with next pointer
• Using head instead of node before position

3. What will be the output list after inserting a node with value 10 at position 2 in the doubly linked list 5 <-> 15 <-> 20?

medium

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

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

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

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

Solution

1. Step 1: Understand position 2 insertion

   Position 2 means the new node goes after the first node (5) and before the second node (15).

2. Step 2: Insert node with value 10 at position 2

   List becomes 5 <-> 10 <-> 15 <-> 20, with null at the end.

3. Final Answer:

   5 <-> 10 <-> 15 <-> 20 <-> null -> Option B

4. Quick Check:

   Insert at 2 shifts old 2nd node right [OK]

Hint: Insert pushes existing nodes right from position [OK]

Common Mistakes:

• Inserting after instead of at position
• Placing new node at wrong position
• Confusing list order after insertion

4. Given this code snippet for insertion at position 3, what is the error?

temp = head
for _ in range(2):
    temp = temp.next
new_node.next = temp.next
new_node.prev = temp
if temp.next:
    temp.next.prev = new_node
temp.next = new_node

medium

A. Loop runs one time too many causing temp to be wrong

B. new_node.prev should be temp.prev

C. new_node.next should be temp

D. Missing check if head is null before loop

Solution

1. Step 1: Analyze loop and temp assignment

   The loop with range(2) moves temp from head (position 1) to position 2, then to position 3.

2. Step 2: Identify the position error

   For insertion at position 3 (new node becomes position 3), temp must be at position 2 to insert after it; range(2) overshoots to position 3, so loop runs one time too many.

3. Final Answer:

   Loop runs one time too many causing temp to be wrong -> Option A

4. Quick Check:

   Loop range should be (position - 2) [OK]

Hint: Loop iterations = position - 2 for temp at (position - 1) [OK]

Common Mistakes:

• Loop runs one time too many
• Confusing prev and next pointers
• Incorrect loop count for position

5. You have a doubly linked list: 1 <-> 3 <-> 5 <-> 7 <-> null. You want to insert a node with value 4 at position 3. After insertion, what will be the correct sequence of the list?

medium

A. 4 <-> 1 <-> 3 <-> 5 <-> 7 <-> null

B. 1 <-> 4 <-> 3 <-> 5 <-> 7 <-> null

C. 1 <-> 3 <-> 4 <-> 5 <-> 7 <-> null

D. 1 <-> 3 <-> 5 <-> 7 <-> 4 <-> null

Solution

1. Step 1: Identify position 3 in the list

   Position 3 means the new node goes after the second node (3) and before the third node (5).

2. Step 2: Insert node with value 4 at position 3

   The list becomes 1 <-> 3 <-> 4 <-> 5 <-> 7 <-> null, maintaining order and links.

3. Final Answer:

   1 <-> 3 <-> 4 <-> 5 <-> 7 <-> null -> Option C

4. Quick Check:

   Insert at position 3 places node between 3 and 5 [OK]

Hint: Insert at position shifts old node at that position right [OK]

Common Mistakes:

• Inserting before position 1 instead of 3
• Appending at end instead of position
• Mixing node values order after insertion