Insert at Specific Position in Doubly Linked List in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a doubly linked list?

A doubly linked list is a chain of nodes where each node has three parts: data, a pointer to the next node, and a pointer to the previous node. This allows traversal in both directions.

beginner

What does 'inserting at a specific position' mean in a doubly linked list?

It means adding a new node at a given place in the list, not just at the start or end. The position is usually counted from the head (start) of the list.

intermediate

What pointers need to be updated when inserting a node in the middle of a doubly linked list?

You must update four pointers: the new node's next and prev, the previous node's next, and the next node's prev, to keep the list connected correctly.

beginner

Why do we check if the position is 1 when inserting in a doubly linked list?

Because inserting at position 1 means adding at the head. We must update the head pointer and handle the previous pointer of the old head.

intermediate

What happens if the position to insert is greater than the length of the doubly linked list?

The insertion is usually done at the end of the list or rejected. It depends on the implementation, but often we add the node at the tail if the position is too large.

Which pointer in a doubly linked list node points to the previous node?

A tail

B prev

C head

D next

The 'prev' pointer points to the previous node in a doubly linked list.

When inserting at position 1 in a doubly linked list, what must be updated?

A Only the tail pointer

B Only the new node's next pointer

C The head pointer and the old head's prev pointer

D No pointers need updating

Inserting at position 1 means adding at the head, so the head pointer and the old head's prev pointer must be updated.

If you want to insert a node at position 3, which nodes' pointers do you need to update?

A Only the new node's pointers

B The head and tail nodes

C No nodes need pointer updates

D The node at position 2 and the node at position 3

You update the new node's pointers and the pointers of nodes at positions 2 and 3 to link the new node correctly.

What happens if you insert at a position greater than the list length?

A Node is inserted at the end

B Insertion fails always

C Node is inserted at the head

D List gets corrupted

Usually, if the position is beyond the list length, the node is inserted at the end.

Which of these is NOT a step when inserting a node in the middle of a doubly linked list?

A Delete the node at the position

B Update new node's next and prev pointers

C Update next node's prev pointer

D Update previous node's next pointer

Deleting a node is not part of insertion; insertion involves updating pointers to add a new node.

Explain step-by-step how to insert a new node at a specific position in a doubly linked list.

Think about how pointers connect nodes before and after the new node.

What pointer updates are necessary when inserting a node between two existing nodes in a doubly linked list?

Focus on the four pointers that keep the chain connected.

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