Insert at Specific Position in Doubly Linked List in DSA Rust - 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

↓

Done

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

Execution Sample

DSA Rust

fn insert_at_position(head: &mut Option<Box<Node>>, pos: usize, val: i32) {
    // Insert val at pos in doubly linked list
}

Inserts a new node with value val at the given position pos in the doubly linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with value 10	None	None	null
2	Check if position == 0	None	None	null
3	Position != 0, start at head (null)	None	None	null
4	List empty, insert new node as head	10	head -> new_node	10 <-> null
5	Insert at position 0: Insert at head	10	head -> new_node	10 <-> null
6	Create new node with value 20	10	None	10 <-> null
7	Position = 1, traverse to node at pos-1 (0)	10	None	10 <-> null
8	Adjust pointers to insert new node after 10	10, 20	10.next -> new_node, new_node.prev -> 10	10 <-> 20 <-> null
9	Create new node with value 15	10, 20	None	10 <-> 20 <-> null
10	Position = 1, traverse to node at pos-1 (0)	10, 20	None	10 <-> 20 <-> null
11	Adjust pointers to insert new node between 10 and 20	10, 15, 20	10.next -> 15, 15.prev -> 10, 15.next -> 20, 20.prev -> 15	10 <-> 15 <-> 20 <-> null
12	Exit: insertion complete	10, 15, 20	Pointers updated	10 <-> 15 <-> 20 <-> null

💡 Insertion done at specified position, pointers adjusted to maintain doubly linked list structure

Variable Tracker

Variable	Start	After Step 1	After Step 6	After Step 9	Final
head	null	null	10	10	10
new_node	null	10	20	15	15
current	null	null	10	10	10
position	given	given	1	1	1

Key Moments - 3 Insights

Why do we check if position is 0 separately?

Because inserting at position 0 means inserting at the head, which requires updating the head pointer directly. This is shown in execution_table rows 2 and 5.

How do we adjust pointers when inserting in the middle?

We set the previous node's next to the new node, the new node's prev to the previous node, the new node's next to the next node, and the next node's prev to the new node. See execution_table row 11.

What happens if the list is empty and position is not zero?

Since the list is empty, any position other than zero is invalid, but here we treat it as inserting at head. This is shown in execution_table row 4.

Visual Quiz - 3 Questions

Look at the execution_table, what is the visual state after step 8?

A 10 <-> 20 <-> null

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

C null

D 10 <-> null

💡 Hint

Check the Visual State column at step 8 in execution_table

At which step do we insert the new node between two existing nodes?

A Step 4

B Step 8

C Step 11

D Step 2

💡 Hint

Look for pointer adjustments involving both prev and next nodes in execution_table

If position was 0, which step shows the insertion at head?

A Step 11

B Step 5

C Step 9

D Step 8

💡 Hint

Check where position == 0 is handled in execution_table

Concept Snapshot

Insert at Specific Position in Doubly Linked List:
- Create new node with given value
- If position == 0, insert at head and update head pointer
- Else, traverse to node at position-1
- Adjust pointers: prev.next = new_node, new_node.prev = prev, new_node.next = next, next.prev = new_node
- Handles empty list by inserting at head
- Maintains doubly linked list structure

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 updating the head pointer. Otherwise, start at the head and traverse to the node just before the target position. Then adjust the pointers of the previous node, the new node, and the next node to insert the new node correctly. If the list is empty, inserting at any position inserts at the head. This process maintains the doubly linked list structure with correct next and prev pointers.

Practice

1. What does inserting at a specific position in a doubly linked list involve?

easy

A. Adjusting the previous and next pointers of nodes around the position

B. Only changing the head pointer of the list

C. Reversing the entire list before insertion

D. Deleting the node at that position first

Solution

1. Step 1: Understand doubly linked list node connections

   Each node has pointers to both previous and next nodes, so insertion requires updating these pointers around the insertion point.

2. Step 2: Adjust pointers for insertion

   To insert at a specific position, update the previous node's next pointer and the next node's previous pointer to point to the new node.

3. Final Answer:

   Adjusting the previous and next pointers of nodes around the position -> Option A

4. Quick Check:

   Pointer updates = Adjust previous and next pointers [OK]

Hint: Remember: update both previous and next pointers [OK]

Common Mistakes:

• Only updating one pointer and ignoring the other
• Not handling edge cases like inserting at head or tail
• Forgetting to update the new node's pointers

2. Which Rust code snippet correctly declares a doubly linked list node struct for insertion?

easy

A. struct Node { data: i32, prev: Option>, next: Option> }

B. struct Node { data: i32, prev: Option<*mut Node>, next: Option<*mut Node> }

C. struct Node { data: i32, prev: Option, next: Option }

D. struct Node { data: i32, prev: Box<Node>, next: Box<Node> }

Solution

1. Step 1: Understand Rust ownership for doubly linked lists

   Doubly linked lists require shared ownership and mutability, so Rc is used to allow multiple owners and interior mutability.

2. Step 2: Identify correct pointer types

   Option> allows optional pointers with shared ownership and mutability, suitable for prev and next pointers.

3. Final Answer:

   struct Node { data: i32, prev: Option>, next: Option> } -> Option A

4. Quick Check:

   Use Rc<RefCell> for shared mutable pointers [OK]

Hint: Use Rc<RefCell> for doubly linked list nodes in Rust [OK]

Common Mistakes:

• Using Box without Rc causes ownership errors
• Using raw pointers without unsafe code
• Not wrapping pointers in Option for nullable links

3. Given this Rust code snippet inserting a node at position 2 in a doubly linked list with nodes 1 <-> 3, what is the list after insertion of node 2?

medium

A. 3 <-> 2 <-> 1

B. 2 <-> 1 <-> 3

C. 1 <-> 2 <-> 3

D. 1 <-> 3 <-> 2

Solution

1. Step 1: Identify insertion position and existing list

   The list is 1 <-> 3, and we insert node 2 at position 2, meaning after node 1 and before node 3.

2. Step 2: Insert node 2 between nodes 1 and 3

   Update node 1's next to node 2, node 2's prev to node 1, node 2's next to node 3, and node 3's prev to node 2.

3. Final Answer:

   1 <-> 2 <-> 3 -> Option C

4. Quick Check:

   Insert at position 2 places node 2 between 1 and 3 [OK]

Hint: Insert node between previous and next nodes at position [OK]

Common Mistakes:

• Inserting node at wrong position
• Not updating both prev and next pointers
• Confusing position indexing starting at 0 or 1

4. In this Rust code for inserting at position 3, the program panics with 'index out of bounds'. What is the likely cause?

medium

A. The new node's pointers are not initialized

B. The list has fewer than 2 nodes, so position 3 is invalid

C. The head pointer is null

D. The insertion code forgets to update the tail pointer

Solution

1. Step 1: Analyze the error message and position

   The panic 'index out of bounds' means the code tried to access a position beyond the list length. Position 3 requires at least 2 nodes before it.

2. Step 2: Check list length against insertion position

   If the list has fewer than 2 nodes, position 3 is invalid, causing the panic.

3. Final Answer:

   The list has fewer than 2 nodes, so position 3 is invalid -> Option B

4. Quick Check:

   Position > list length causes index out of bounds [OK]

Hint: Check list length before inserting at position [OK]

Common Mistakes:

• Not validating position against list length
• Assuming tail pointer updates fix index errors
• Ignoring null or empty list cases

5. You have a doubly linked list with nodes 10 <-> 20 <-> 30. Write the steps to insert a node with value 25 at position 3 and show the final list.

hard

A. 25 <-> 10 <-> 20 <-> 30

B. 10 <-> 25 <-> 20 <-> 30

C. 10 <-> 20 <-> 30 <-> 25

D. 10 <-> 20 <-> 25 <-> 30

Solution

1. Step 1: Locate position 3 in the list

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

2. Step 2: Update pointers to insert node 25

   Set node 20's next to new node 25, new node 25's prev to node 20, new node 25's next to node 30, and node 30's prev to new node 25.

3. Final Answer:

   10 <-> 20 <-> 25 <-> 30 -> Option D

4. Quick Check:

   Insert at position 3 places 25 between 20 and 30 [OK]

Hint: Insert between nodes at position - 1 and position [OK]

Common Mistakes:

• Inserting node at wrong position
• Not updating both prev and next pointers correctly
• Confusing position indexing starting at 0 or 1