Insert at Beginning of Doubly Linked List in DSA Rust - Execution Trace

Concept Flow - Insert at Beginning of Doubly Linked List

Create new node

↓

Set new_node.next = head

↓

If head != null

Yes↓

Set head.prev = new_node

↓

Set head = new_node

↓

Done

The new node is created and linked before the current head. If the list is not empty, the old head's previous pointer is updated. Finally, head points to the new node.

Execution Sample

DSA Rust

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

// Insert new node at beginning

This code inserts a new node at the start of a doubly linked list, updating pointers accordingly.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=5	∅	new_node.prev = None, new_node.next = None	List is empty
2	Set new_node.next = head (None)	∅	new_node.next = None	new_node (5) → ∅
3	Check if head != None	∅	head is None, skip prev update	new_node (5) → ∅
4	Set head = new_node	5	head points to new_node	head → 5 → ∅
5	Insert another node with data=10 at beginning	5	Create new_node with data=10	head → 5 → ∅
6	Set new_node.next = head (5)	5	new_node.next points to 5	new_node (10) → 5 → ∅
7	Set head.prev = new_node (10)	5	5.prev points to 10	10 ⇄ 5 → ∅
8	Set head = new_node (10)	10 ⇄ 5	head points to 10	head → 10 ⇄ 5 → ∅
9	End of insertions	10 ⇄ 5	No changes	head → 10 ⇄ 5 → ∅

💡 Insertion complete; head updated to new node at beginning

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
head	None	None	None	Node(5)	Node(5)	Node(5)	Node(5)	Node(10)	Node(10)
new_node.data	N/A	5	5	5	10	10	10	10	10
new_node.next	N/A	None	None	None	None	Node(5)	Node(5)	Node(5)	Node(5)
new_node.prev	N/A	None	None	None	None	None	None	None	None
head.prev	N/A	N/A	N/A	None	None	None	Node(10)	None	None

Key Moments - 3 Insights

Why do we set new_node.next = head before updating head?

Because new_node must point to the old first node to keep the list connected. See execution_table step 2 and 6 where new_node.next is set before head changes.

Why do we update head.prev to new_node?

To maintain the backward link in the doubly linked list. Without this, the old head wouldn't know about the new node before it. Refer to execution_table step 7.

What happens if the list is empty when inserting?

The new node's next and prev remain None, and head points to this new node. This is shown in steps 1 to 4 where the list starts empty.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what pointer change happens?

A head is set to new_node

B new_node.next is set to head

C head.prev is set to new_node

D new_node.prev is set to head

💡 Hint

Check the 'Pointer Changes' column at step 7 in execution_table

At which step does head first point to the new node with data=5?

A Step 2

B Step 4

C Step 6

D Step 8

💡 Hint

Look at the 'head' variable in variable_tracker after step 4

If the list was empty, what would new_node.next be after insertion?

A Points to None

B Points to old head node

C Points to itself

D Undefined

💡 Hint

See execution_table step 2 and 3 where new_node.next is set when head is None

Concept Snapshot

Insert at Beginning of Doubly Linked List:
- Create new node
- Set new_node.next to current head
- If head exists, set head.prev to new_node
- Update head to new_node
- Maintains forward and backward links
- Handles empty list by setting head directly

Full Transcript

To insert a node at the beginning of a doubly linked list, first create the new node with the given data. Then set the new node's next pointer to the current head of the list. If the list is not empty, update the old head's prev pointer to point back to the new node. Finally, update the head pointer to the new node. This process ensures the list remains connected in both directions. If the list is empty, the new node becomes the head with no next or prev nodes. The execution table shows each step, including pointer changes and the visual state of the list. The variable tracker follows how head and pointers change after each operation. Key moments clarify why pointer updates happen in a specific order. The visual quiz tests understanding of pointer changes and list state at different steps.

Practice

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

easy

A. To remove the first node from the list

B. To add a new node at the end of the list

C. To add a new node as the first element, updating head pointer

D. To reverse the entire list

Solution

1. Step 1: Understand the operation

   Inserting at the beginning means adding a new node before the current first node.

2. Step 2: Effect on head pointer

   The head pointer must be updated to point to this new node, making it the first element.

3. Final Answer:

   To add a new node as the first element, updating head pointer -> Option C

4. Quick Check:

   Insert at beginning = update head to new node [OK]

Hint: New node becomes head; update pointers accordingly [OK]

Common Mistakes:

• Confusing insertion at beginning with insertion at end
• Not updating the head pointer
• Not adjusting previous pointer of old head

2. Which of the following Rust code snippets correctly creates a new node and inserts it at the beginning of a doubly linked list?

easy

A. let new_node = Box::new(Node { data: val, prev: None, next: head }); head = Some(new_node);

B. let new_node = Node { data: val, prev: head, next: None }; head = Some(Box::new(new_node));

C. head = Some(Box::new(Node { data: val, prev: None, next: None }));

D. let new_node = Box::new(Node { data: val, prev: None, next: None }); tail = Some(new_node);

Solution

1. Step 1: Create new node with prev None and next as current head

   The new node's previous pointer should be None because it will be the first node. Its next pointer should point to the current head.

2. Step 2: Update head to new node

   After creating the new node, the head pointer must be updated to point to this new node.

3. Final Answer:

   let new_node = Box::new(Node { data: val, prev: None, next: head }); head = Some(new_node); -> Option A

4. Quick Check:

   New node prev None, next head, update head [OK]

Hint: Prev None, next old head, then update head [OK]

Common Mistakes:

• Setting prev to head instead of None
• Not boxing the new node
• Updating tail instead of head

3. Given the following Rust code for inserting at the beginning of a doubly linked list, what will be the printed list after insertion?

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

let mut head = Some(Box::new(Node { data: 2, prev: None, next: None }));

// Insert 1 at beginning
let new_node = Box::new(Node { data: 1, prev: None, next: head });
head = Some(new_node);

// Print list
let mut current = &head;
while let Some(node) = current {
    print!("{} -> ", node.data);
    current = &node.next;
}
print!("null");

medium

A. 1 -> 2 -> null

B. 2 -> 1 -> null

C. 1 -> null

D. 2 -> null

Solution

1. Step 1: Understand insertion

   The new node with data 1 is created with next pointing to old head (node with data 2). So list starts with 1, then 2.

2. Step 2: Trace printing loop

   Printing starts at head (1), then moves to next (2), then next is None, so ends with null.

3. Final Answer:

   1 -> 2 -> null -> Option A

4. Quick Check:

   New node at front, list prints 1 then 2 [OK]

Hint: New node points to old head; print follows next pointers [OK]

Common Mistakes:

• Confusing order of nodes after insertion
• Not updating head pointer
• Printing prev instead of next

4. Identify the error in this Rust code snippet that tries to insert a node at the beginning of a doubly linked list:

let mut head = Some(Box::new(Node { data: 3, prev: None, next: None }));
let new_node = Box::new(Node { data: 1, prev: None, next: head });
head = Some(new_node);
if let Some(ref mut old_head) = head {
    old_head.prev = Some(Box::new(Node { data: 1, prev: None, next: None }));
}

medium

A. Fails to update head pointer

B. Incorrectly creates a new node for prev instead of linking to new_node

C. Does not set new_node.next to old head

D. Uses immutable reference instead of mutable

Solution

1. Step 1: Check prev pointer update

   The code sets old_head.prev to a new node with data 1 instead of linking it to the existing new_node.

2. Step 2: Understand correct linking

   Prev pointer should point to the new_node itself, not a new separate node.

3. Final Answer:

   Incorrectly creates a new node for prev instead of linking to new_node -> Option B

4. Quick Check:

   Prev must link to new_node, not new node copy [OK]

Hint: Prev pointer links to existing node, not a new duplicate [OK]

Common Mistakes:

• Creating duplicate nodes instead of linking
• Not using mutable references for modification
• Not updating prev pointer at all

5. You have a doubly linked list with nodes containing values 3 <-> 5 <-> 7. You want to insert 1 at the beginning. Which sequence of pointer updates is correct to maintain list integrity?

hard

A. Create new node with prev old head, next old head; update head to new node

B. Create new node with prev old head, next None; set old head next to new node; update head to new node

C. Create new node with prev None, next None; update head to new node only

D. Create new node with prev None, next old head; set old head prev to new node; update head to new node

Solution

1. Step 1: Create new node with prev None and next pointing to old head

   The new node is first, so prev is None. Next points to old head (node with 3).

2. Step 2: Update old head's prev pointer to new node and head pointer to new node

   Old head's prev must point back to new node. Head pointer must be updated to new node.

3. Final Answer:

   Create new node with prev None, next old head; set old head prev to new node; update head to new node -> Option D

4. Quick Check:

   New node prev None, next old head; old head prev new node; update head [OK]

Hint: New node prev None, next old head; old head prev new node; update head [OK]

Common Mistakes:

• Setting new node prev to old head
• Not updating old head prev pointer
• Not updating head pointer