Delete Node by Value in DSA Rust - Execution Trace

Concept Flow - Delete Node by Value

Start at head

↓

Is head null?

Yes→Stop: List empty

No↓

Is head value == target?

Yes→Delete head, update head

No↓

Set current = head

↓

While current.next != null

↓

Is current.next.value == target?

Yes→Delete current.next

No↓

Move current to current.next

Back to While↓

Target not found or deleted

↓

End

↩Back to While

Start from the head node, check if it matches the target value to delete. If yes, remove it by updating head. Otherwise, traverse the list to find the node before the target and remove the target node by adjusting pointers.

Execution Sample

DSA Rust

fn delete_node(head: &mut Option<Box<Node>>, val: i32) {
    if head.is_none() { return; }
    if head.as_ref().unwrap().val == val {
        *head = head.take().unwrap().next;
        return;
    }
    let mut current = head.as_mut().unwrap();
    while let Some(ref mut next_node) = current.next {
        if next_node.val == val {
            current.next = next_node.next.take();
            return;
        }
        current = current.next.as_mut().unwrap();
    }
}

Deletes the first node with the given value from a singly linked list.

Execution Table

Step	Current Node Value	Check Condition	Action	List State
1	head = 1	head is not None	Continue	1 -> 2 -> 3 -> 4 -> null
2	head.val == 3?	1 == 3? False	Go to traversal	1 -> 2 -> 3 -> 4 -> null
3	current = 1	current.next.val == 3?	2 == 3? False	1 -> 2 -> 3 -> 4 -> null
4	current = 2	current.next.val == 3?	3 == 3? True	Delete node with val 3
5	After deletion	Stop	Return	1 -> 2 -> 4 -> null

💡 Node with value 3 found and deleted; traversal stops.

Variable Tracker

Variable	Start	After Step 3	After Step 4	Final
head	1 -> 2 -> 3 -> 4 -> null	1 -> 2 -> 3 -> 4 -> null	1 -> 2 -> 4 -> null	1 -> 2 -> 4 -> null
current	1	2	2	2

Key Moments - 2 Insights

Why do we check if the head node contains the target value separately?

Because deleting the head node requires updating the head pointer itself, which is different from deleting nodes later in the list. This is shown in execution_table step 2 where we check head.val == target.

What happens if the target value is not found in the list?

The traversal continues until current.next is None, then the function returns without changes. This is implied after step 5 in the execution_table where no deletion occurs.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'current' at step 4?

A 1

B 2

C 3

D 4

💡 Hint

Check the 'Current Node Value' column at step 4 in execution_table.

At which step does the node with value 3 get deleted?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Action' column in execution_table where deletion is mentioned.

If the target value was 1 instead of 3, what would happen at step 2?

A Head node would be deleted and head updated

B Traversal would start from head

C Nothing would change

D Function would return without changes

💡 Hint

Refer to the check for head.val == target in execution_table step 2.

Concept Snapshot

Delete Node by Value in Linked List:
- Check if list is empty; if yes, stop.
- If head node matches value, delete by updating head.
- Else, traverse list to find node before target.
- Remove target by linking previous node to target.next.
- Stops after first deletion.

Full Transcript

This visual trace shows how to delete a node by value in a singly linked list. We start by checking if the list is empty. If not, we check if the head node contains the target value. If yes, we delete the head by updating the head pointer. Otherwise, we traverse the list node by node, checking the next node's value. When we find the target, we remove it by changing the current node's next pointer to skip the target node. The process stops after deleting the first matching node or after confirming the value is not present. Variables like 'head' and 'current' change as we move through the list, and the list state updates after deletion. This method ensures safe removal without losing the list structure.

Practice

1. What does the operation "Delete Node by Value" do in a linked list?

easy

A. Removes the first node that contains the given value

B. Adds a new node with the given value at the end

C. Reverses the linked list

D. Counts the number of nodes with the given value

Solution

1. Step 1: Understand the operation

   Deleting a node by value means finding the first node that matches the value and removing it from the list.

2. Step 2: Compare options

   Only Removes the first node that contains the given value describes removing the first node with the given value, which matches the operation.

3. Final Answer:

   Removes the first node that contains the given value -> Option A

4. Quick Check:

   Delete node by value = Remove first matching node [OK]

Hint: Delete node by value means remove first matching node [OK]

Common Mistakes:

• Confusing deletion by value with adding nodes
• Thinking it deletes all nodes with the value
• Mixing deletion by value with reversing the list

2. Which Rust code snippet correctly deletes the first node with value `val` from a singly linked list starting at `head`?

easy

A. let mut current = &mut head;
while let Some(ref mut node) = current {
if node.val == val {
*current = node.next.take();
break;
}
current = &mut node.next;
}

B. let mut current = head;
while current.is_some() {
if current.val == val {
current = current.next;
break;
}
current = current.next;
}

C. for node in head.iter() {
if node.val == val {
head.remove(node);
break;
}
}

D. while let Some(node) = head {
if node.val == val {
head = node.next;
}
}

Solution

1. Step 1: Analyze pointer usage in Rust linked list deletion

   Rust linked lists use mutable references to update links. let mut current = &mut head; while let Some(ref mut node) = current { if node.val == val { *current = node.next.take(); break; } current = &mut node.next; } uses `&mut` references and `take()` to remove the node correctly.

2. Step 2: Check other options for correctness

   let mut current = head; while current.is_some() { if current.val == val { current = current.next; break; } current = current.next; } uses immutable references and does not update links properly. for node in head.iter() { if node.val == val { head.remove(node); break; } } uses a for loop which is invalid for linked lists. while let Some(node) = head { if node.val == val { head = node.next; } } does not handle mutable references correctly.

3. Final Answer:

   Uses `&mut` references and `take()` to remove the node correctly -> Option A

4. Quick Check:

   Use mutable references and take() to delete node [OK]

Hint: Use mutable references and take() to delete node [OK]

Common Mistakes:

• Using immutable references to modify list
• Trying to iterate with for loop on linked list
• Not updating the previous node's next pointer

3. Given the Rust code below, what will be the linked list after deleting the node with value 3?

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

let mut head = Some(Box::new(Node { val: 1, next: Some(Box::new(Node { val: 3, next: Some(Box::new(Node { val: 5, next: None })) })) }));

let val = 3;
let mut current = &mut head;
while let Some(ref mut node) = current {
  if node.val == val {
    *current = node.next.take();
    break;
  }
  current = &mut node.next;
}

medium

A. 1 -> null

B. 1 -> 3 -> 5 -> null

C. 1 -> 5 -> null

D. 3 -> 5 -> null

Solution

1. Step 1: Understand the initial list structure

   The list is 1 -> 3 -> 5 -> null.

2. Step 2: Trace deletion of node with value 3

   The loop finds node with val=3 and removes it by linking previous node's next to node 3's next (which is node 5).

3. Final Answer:

   1 -> 5 -> null -> Option C

4. Quick Check:

   Deleted node 3, list is 1 -> 5 [OK]

Hint: After deletion, previous node points to deleted node's next [OK]

Common Mistakes:

• Not updating previous node's next pointer
• Deleting wrong node due to incorrect comparison
• Confusing node values and positions

4. The following Rust code attempts to delete a node by value from a linked list but causes a compile error. What is the main issue?

let mut current = &head;
while let Some(ref node) = current {
  if node.val == val {
    current = &node.next;
    break;
  }
  current = &node.next;
}

medium

A. Missing semicolon after `current = &node.next`

B. Using immutable reference `&head` prevents modifying the list

C. Incorrect use of `while let` syntax

D. `val` is not defined in the scope

Solution

1. Step 1: Check reference mutability

   The code uses `&head` which is immutable, so it cannot modify the list links.

2. Step 2: Understand why mutable reference is needed

   To delete a node, we must change pointers, requiring `&mut` references, which are missing here.

3. Final Answer:

   Using immutable reference `&head` prevents modifying the list -> Option B

4. Quick Check:

   Modify list needs mutable references [OK]

Hint: Use &mut references to modify linked list nodes [OK]

Common Mistakes:

• Ignoring mutability requirements in Rust
• Assuming immutable references can change list
• Overlooking compiler error messages

5. You have a singly linked list with nodes: 2 -> 4 -> 6 -> 4 -> 8 -> null. You want to delete all nodes with value 4 using Rust. Which approach correctly deletes all such nodes?

hard

A. Traverse list with immutable references and skip nodes with value 4 without modifying links

B. Delete only the first node with value 4 and stop

C. Replace all node values 4 with 0 instead of deleting nodes

D. Use a loop with mutable reference to current node pointer, repeatedly deleting nodes with value 4 until none remain

Solution

1. Step 1: Understand requirement to delete all nodes with value 4

   We must remove every node containing 4, not just the first.

2. Step 2: Use mutable references to update links repeatedly

   Loop through list with mutable pointer, deleting nodes with value 4 by updating links until none remain.

3. Step 3: Reject other options

   Delete only the first node with value 4 and stop deletes only first node. Traverse list with immutable references and skip nodes with value 4 without modifying links does not modify list. Replace all node values 4 with 0 instead of deleting nodes changes values but does not delete nodes.

4. Final Answer:

   Use a loop with mutable reference to current node pointer, repeatedly deleting nodes with value 4 until none remain -> Option D

5. Quick Check:

   Delete all matching nodes by looping with mutable refs [OK]

Hint: Loop with mutable refs to delete all matching nodes [OK]

Common Mistakes:

• Deleting only first matching node
• Using immutable references to try deleting
• Confusing value replacement with deletion