Delete Node by Value in DSA Rust

Mental Model

To remove a node with a specific value, find it by moving through the list, then change the previous node to skip it.

Analogy: Imagine a chain of paper clips linked together. To remove one clip, you unhook it and connect the clip before it directly to the one after it.

head -> 1 -> 2 -> 3 -> null
↑

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> null, delete value 2

Goal: Remove the node containing value 2 and keep the list connected

Step 1: Check if head node has value 2

head -> [1] -> 2 -> 3 -> null
↑

Why: We start at the head to see if it needs removal

Step 2: Move to next node to find value 2

head -> 1 -> [2] -> 3 -> null
↑

Why: Value 2 is not at head, so we look further

Step 3: Change node 1's next pointer to skip node 2 and point to node 3

head -> 1 -> 3 -> null
↑

Why: Removing node 2 by linking node 1 directly to node 3

Result:

head -> 1 -> 3 -> null

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct Node {
    val: i32,
    next: Option<Rc<RefCell<Node>>>,
}

impl Node {
    fn new(val: i32) -> Rc<RefCell<Node>> {
        Rc::new(RefCell::new(Node { val, next: None }))
    }
}

fn delete_node_by_value(head: Option<Rc<RefCell<Node>>>, value: i32) -> Option<Rc<RefCell<Node>>> {
    // Handle empty list
    let mut dummy = Node::new(0); // dummy node to simplify edge cases
    dummy.borrow_mut().next = head;

    let mut current = dummy.clone();

    while let Some(next_node) = current.borrow().next.clone() {
        if next_node.borrow().val == value {
            // Skip the node with the target value
            let next_next = next_node.borrow().next.clone();
            current.borrow_mut().next = next_next;
            break; // only delete first occurrence
        } else {
            current = next_node;
        }
    }

    dummy.borrow().next.clone()
}

fn print_list(head: &Option<Rc<RefCell<Node>>>) {
    let mut current = head.clone();
    while let Some(node) = current {
        print!("{} -> ", node.borrow().val);
        current = node.borrow().next.clone();
    }
    println!("null");
}

fn main() {
    // Create list 1 -> 2 -> 3 -> null
    let n1 = Node::new(1);
    let n2 = Node::new(2);
    let n3 = Node::new(3);
    n1.borrow_mut().next = Some(n2.clone());
    n2.borrow_mut().next = Some(n3.clone());

    println!("Original list:");
    print_list(&Some(n1.clone()));

    let new_head = delete_node_by_value(Some(n1.clone()), 2);

    println!("List after deleting value 2:");
    print_list(&new_head);
}

let mut dummy = Node::new(0); // dummy node to simplify edge cases dummy.borrow_mut().next = head;

Create dummy node pointing to head to handle deletion at head easily

while let Some(next_node) = current.borrow().next.clone() {

Traverse nodes by looking ahead to next node

if next_node.borrow().val == value {

Check if next node has the value to delete

current.borrow_mut().next = next_node.borrow().next.clone();

Skip the node with target value by linking current to next of next

current = next_node;

Advance current pointer when no deletion

Output

Original list:

1 -> 2 -> 3 -> null

List after deleting value 2:

1 -> 3 -> null

Complexity Analysis

Time: O(n) because we may need to check each node once until we find the value

Space: O(1) because we only use a few extra pointers, no extra list copies

vs Alternative: Compared to rebuilding a new list without the value, this modifies pointers in place, saving time and space

Edge Cases

empty list

function returns None without error

DSA Rust

let mut dummy = Node::new(0); // dummy node to simplify edge cases

value at head node

head is removed by dummy pointer adjustment

DSA Rust

dummy.borrow_mut().next = head;

value not found in list

list remains unchanged

DSA Rust

while let Some(next_node) = current.borrow().next.clone() {

When to Use This Pattern

When you need to remove a node by value from a singly linked list, use a dummy node and pointer traversal to unlink the target node cleanly.

Common Mistakes

Mistake: Not handling deletion of the head node separately causes errors or lost head pointer.
Fix: Use a dummy node pointing to head to unify deletion logic for all nodes.

Summary

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

Use when you want to remove a specific value from a linked list without rebuilding it.

The key is to use a dummy node and adjust pointers to skip the node to delete.

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