Delete from Beginning of Doubly Linked List in DSA Rust - Execution Trace

Concept Flow - Delete from Beginning of Doubly Linked List

Start at head node

↓

Check if list is empty?

↓

Move head to head.next

↓

Set new head.prev to null

↓

Old head node removed

↓

Done

Start at the head node, check if list is empty. If not, move head to next node and update pointers to remove old head.

Execution Sample

DSA Rust

fn delete_from_beginning(head: &mut Option<Box<Node>>) {
    if head.is_none() { return; }
    let mut old_head = head.take().unwrap();
    *head = old_head.next.take();
    if let Some(ref mut new_head) = head {
        new_head.prev = None;
    }
}

Deletes the first node from a doubly linked list by moving head to next node and updating pointers.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with list: 10 <-> 20 <-> 30	10 <-> 20 <-> 30	head → node with 10	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ prev:∅ │←── │ prev:10│←── │ prev:20│ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head
2	Check if list is empty	10 <-> 20 <-> 30	No change	Same as step 1
3	Remove old head (10), move head to 20	20 <-> 30	head → node with 20 old head (10) detached	┌────────┐ ┌────────┐ │ data:20│ │ data:30│ │ prev:∅ │←── │ prev:20│ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ head
4	Set new head.prev to null	20 <-> 30	new head.prev = ∅	Same as step 3
5	Old head node (10) removed, list updated	20 <-> 30	No dangling pointers	Final list: ┌────────┐ ┌────────┐ │ data:20│ │ data:30│ │ prev:∅ │←── │ prev:20│ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ head
6	Exit	20 <-> 30	Deletion complete	List after deletion

💡 Head moved to next node; old head removed; list updated successfully

Variable Tracker

Variable	Start	After Step 3	After Step 4	Final
head	Points to node 10	Points to node 20	Points to node 20	Points to node 20
old_head	None	Points to node 10 (detached)	Points to node 10 (detached)	Dropped (removed)
head.prev	None	Points to node 10 (old)	None	None
list size	3 nodes	2 nodes	2 nodes	2 nodes

Key Moments - 3 Insights

Why do we set new head.prev to null after moving head?

Because the new head is now the first node, it should not have a previous node. This is shown in execution_table step 4 where new head.prev is set to ∅.

What happens if the list is empty when we try to delete from beginning?

The function checks if head is None at step 2 and exits immediately without changes, so no error occurs.

Why do we detach old head's next pointer before moving head?

Detaching old head's next pointer (step 3) prevents dangling references and helps Rust safely drop the old node without affecting the new list.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what does the head pointer point to after deletion?

A Node with data 10

B Node with data 20

C Node with data 30

D Null (empty list)

💡 Hint

Refer to execution_table row 3 under 'Pointer Changes' and 'Visual State'

At which step does the new head's prev pointer get set to null?

A Step 4

B Step 3

C Step 2

D Step 5

💡 Hint

Check execution_table row 4 under 'Operation' and 'Pointer Changes'

If the list was empty initially, what would happen according to the execution_table?

A Old head node is removed

B Head pointer moves to next node

C Function exits without changes

D New node is added

💡 Hint

Look at step 2 where the empty list check happens

Concept Snapshot

Delete from Beginning of Doubly Linked List:
- Check if list is empty; if yes, do nothing.
- Move head pointer to next node.
- Set new head's prev pointer to null.
- Old head node is detached and removed.
- List size decreases by one.
- Ensures no dangling pointers remain.

Full Transcript

To delete the first node from a doubly linked list, start by checking if the list is empty. If it is, exit immediately. Otherwise, move the head pointer to the next node. Then set the new head's previous pointer to null to mark it as the first node. Detach the old head's next pointer to safely remove it. This process updates the list correctly without leaving dangling pointers or memory issues. The list size decreases by one after deletion.

Practice

1. What happens to the head pointer when you delete the first node from a doubly linked list?

easy

A. It points to the last node

B. It moves to the next node in the list

C. It becomes null immediately

D. It remains unchanged

Solution

1. Step 1: Understand the role of head in a doubly linked list

   The head pointer always points to the first node in the list.

2. Step 2: Effect of deleting the first node

   When the first node is deleted, the head must move to the next node to keep the list accessible.

3. Final Answer:

   It moves to the next node in the list -> Option B

4. Quick Check:

   Deleting first node updates head to next node [OK]

Hint: Head always points to first node; update it after deletion [OK]

Common Mistakes:

• Not updating head pointer after deletion
• Setting head to null without checking list length
• Confusing head with tail pointer

2. Which of the following Rust code snippets correctly deletes the first node from a doubly linked list?

easy

A. if let Some(mut node) = head.take() { head = node.next.take(); if let Some(ref mut new_head) = head { new_head.prev = None; } }

B. head = head.next; head.prev = None;

C. head = None; tail = None;

D. head.prev = None; head = head.next;

Solution

1. Step 1: Analyze safe Rust deletion pattern

   if let Some(mut node) = head.take() { head = node.next.take(); if let Some(ref mut new_head) = head { new_head.prev = None; } } uses take() to safely remove the first node and updates head and prev pointers correctly.

2. Step 2: Check other options for errors

   head = head.next; head.prev = None; tries to access head.next without handling Option. head = None; tail = None; deletes entire list incorrectly. head.prev = None; head = head.next; accesses head.prev before updating head, causing error.

3. Final Answer:

   Option A code snippet -> Option A

4. Quick Check:

   Safe pointer update with take() = if let Some(mut node) = head.take() { head = node.next.take(); if let Some(ref mut new_head) = head { new_head.prev = None; } } [OK]

Hint: Use take() to safely remove and update pointers [OK]

Common Mistakes:

• Ignoring Option unwrap safety
• Not updating prev pointer of new head
• Setting head to None without checking

3. Given the following Rust code for a doubly linked list deletion from beginning, what will be the printed list after deletion?

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

// List: 10 <-> 20 <-> 30
let mut head = Some(Box::new(Node { val: 10, prev: None, next: Some(Box::new(Node { val: 20, prev: None, next: Some(Box::new(Node { val: 30, prev: None, next: None })) })) }));

// Delete first node
if let Some(mut node) = head.take() {
  head = node.next.take();
  if let Some(ref mut new_head) = head {
    new_head.prev = None;
  }
}

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

medium

A. null

B. 10 -> 20 -> 30 -> null

C. 20 -> 30 -> null

D. 30 -> null

Solution

1. Step 1: Initial list structure

   The list starts as 10 <-> 20 <-> 30, with head at 10.

2. Step 2: Deletion of first node

   Deleting first node moves head to 20, and sets 20.prev to None.

3. Step 3: Printing the list

   Starting from new head (20), printing nodes gives 20 -> 30 -> null.

4. Final Answer:

   20 -> 30 -> null -> Option C

5. Quick Check:

   Head updated to second node, list prints from 20 [OK]

Hint: After deletion, head points to second node; print from there [OK]

Common Mistakes:

• Printing old head after deletion
• Not updating prev pointer causing broken links
• Confusing next and prev pointers

4. Identify the error in this Rust code snippet that tries to delete the first node from a doubly linked list:

if head.is_some() {
  head = head.unwrap().next;
  if let Some(ref mut new_head) = head {
    new_head.prev = None;
  }
}

medium

A. Using unwrap() consumes head, causing a move error

B. Not setting new_head.prev to None

C. Missing check if head is None before deletion

D. Incorrectly updating tail pointer

Solution

1. Step 1: Understand unwrap() behavior on Option

   Calling unwrap() on head moves the value out, consuming it and invalidating head.

2. Step 2: Consequence of move error

   Assigning head = head.unwrap().next; causes a move error because head is used after being moved.

3. Final Answer:

   Using unwrap() consumes head, causing a move error -> Option A

4. Quick Check:

   unwrap() moves value, invalidating head [OK]

Hint: Avoid unwrap() on Option when reassigning; use take() [OK]

Common Mistakes:

• Using unwrap() causing move errors
• Not handling Option safely
• Forgetting to update prev pointer

5. You have a doubly linked list with nodes: 5 <-> 15 <-> 25 <-> 35. After deleting the first node twice using correct Rust code, what will be the final list printed?

let mut head = Some(Box::new(Node { val: 5, prev: None, next: Some(Box::new(Node { val: 15, prev: None, next: Some(Box::new(Node { val: 25, prev: None, next: Some(Box::new(Node { val: 35, prev: None, next: None })) })) })) }));

// Delete first node twice
for _ in 0..2 {
  if let Some(mut node) = head.take() {
    head = node.next.take();
    if let Some(ref mut new_head) = head {
      new_head.prev = None;
    }
  }
}

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

hard

A. 15 -> 25 -> 35 -> null

B. null

C. 35 -> null

D. 25 -> 35 -> null

Solution

1. Step 1: Initial list and first deletion

   List starts as 5 <-> 15 <-> 25 <-> 35. First deletion removes 5, head moves to 15.

2. Step 2: Second deletion

   Second deletion removes 15, head moves to 25, and 25.prev is set to None.

3. Step 3: Printing final list

   Starting from 25, printing nodes gives 25 -> 35 -> null.

4. Final Answer:

   25 -> 35 -> null -> Option D

5. Quick Check:

   Two deletions move head twice forward [OK]

Hint: Each deletion moves head to next node; repeat for multiple deletions [OK]

Common Mistakes:

• Not updating prev pointer after each deletion
• Deleting only once instead of twice
• Printing old head after deletions