Insert at Specific Position in Doubly Linked List in DSA Python - Execution Trace

Concept Flow - Insert at Specific Position in Doubly Linked List

Create new node

↓

Check if position is 0

↓

Insert at head

↓

Traverse to position-1

↓

Adjust pointers to insert

↓

Done

Create a new node, then either insert at the head if position is 0, or traverse to the node before the position and adjust pointers to insert the new node.

Execution Sample

DSA Python

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

def insert_at_pos(head, data, pos):
    # Insert node with data at position pos

This code inserts a new node with given data at a specific position in a doubly linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=25	10 <-> 20 <-> 30 <-> 40	None	10 <-> 20 <-> 30 <-> 40
2	Position=2, start at head	10 <-> 20 <-> 30 <-> 40	current = 10	10 <-> 20 <-> 30 <-> 40
3	Traverse to position-1 (pos=2, move 1 step)	10 <-> 20 <-> 30 <-> 40	current moves to 20	10 <-> 20 <-> 30 <-> 40
4	Adjust pointers to insert new node after current (20)	10 <-> 20 <-> 30 <-> 40	new_node.prev = 20, new_node.next = 30 20.next = new_node 30.prev = new_node	10 <-> 20 <-> 25 <-> 30 <-> 40
5	Insertion complete	10 <-> 20 <-> 25 <-> 30 <-> 40	None	10 <-> 20 <-> 25 <-> 30 <-> 40
6	Exit	10 <-> 20 <-> 25 <-> 30 <-> 40	None	Position reached, insertion done

💡 Insertion done at position 2, pointers updated correctly

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
head	10	10	10	10	10
current	None	10	20	20	20
new_node.data	None	25	25	25	25
new_node.prev	None	None	None	20	20
new_node.next	None	None	None	30	30

Key Moments - 3 Insights

Why do we stop traversal at position-1 instead of position?

Because we need to insert the new node after the node at position-1, so we stop traversal there to adjust pointers correctly (see Step 3 and Step 4 in execution_table).

What happens if position is 0?

If position is 0, the new node is inserted at the head, adjusting head pointer and next/prev pointers accordingly (not shown in this trace but part of concept_flow).

Why do we update both next and prev pointers when inserting?

Because it's a doubly linked list, each node has pointers to both previous and next nodes, so both must be updated to maintain list integrity (see Step 4 pointer changes).

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, where is the current pointer?

A At node with data 10

B At node with data 20

C At node with data 30

D At node with data 25

💡 Hint

Check the 'Pointer Changes' column at Step 3 in execution_table

At which step do we update the new_node's prev and next pointers?

A Step 4

B Step 3

C Step 2

D Step 5

💡 Hint

Look at the 'Pointer Changes' column describing new_node.prev and new_node.next assignments

If we tried to insert at position 0, what would change in the execution_table?

A New node would be inserted after the last node

B Traversal would go to position-1 as usual

C Traversal steps would be skipped and insertion happens at head

D No insertion would happen

💡 Hint

Refer to concept_flow where position 0 leads to direct insertion at head

Concept Snapshot

Insert at Specific Position in Doubly Linked List:
- Create new node with data
- If position is 0, insert at head
- Else traverse to node at position-1
- Adjust new_node.prev and new_node.next
- Update surrounding nodes' pointers
- Maintain list integrity both ways

Full Transcript

To insert a node at a specific position in a doubly linked list, first create the new node. If the position is zero, insert the node at the head by adjusting the head pointer and the next and prev pointers of involved nodes. Otherwise, start from the head and move forward until reaching the node just before the desired position (position-1). Then, adjust the new node's prev pointer to this node and its next pointer to the next node. Also, update the next pointer of the node at position-1 to the new node, and the prev pointer of the next node to the new node. This keeps the doubly linked list connected correctly in both directions. The execution table shows these steps with the list nodes and pointer changes. Key moments clarify why traversal stops at position-1 and why both pointers must be updated. The visual quiz tests understanding of pointer positions and insertion logic.

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