Delete Node by Value in DSA Rust - Build from Scratch

Delete Node by Value

📖 Scenario: You are managing a simple list of tasks represented as a singly linked list. Sometimes, you need to remove a task by its name when it is completed or no longer needed.

🎯 Goal: Build a Rust program that creates a singly linked list of tasks, then deletes a task node by its exact name value.

📋 What You'll Learn

Create a singly linked list with exactly these tasks in order: "Cook", "Eat", "Clean", "Sleep"

Create a variable called task_to_delete with the value "Clean"

Write a function called delete_node_by_value that removes the first node with the value matching task_to_delete

Print the linked list after deletion in the format: task1 -> task2 -> ... -> null

💡 Why This Matters

🌍 Real World

Linked lists are used in many applications like task scheduling, undo functionality, and managing dynamic data where insertion and deletion happen frequently.

💼 Career

Understanding linked lists and how to manipulate them is fundamental for software engineers, especially in systems programming, embedded systems, and performance-critical applications.

1

Create the linked list of tasks

Create a singly linked list called head with nodes containing these exact task names in order: "Cook", "Eat", "Clean", "Sleep". Use Option> for links and a struct Node with fields task: String and next: Option>.

DSA Rust

// Define struct Node
// Create linked list head with tasks "Cook" -> "Eat" -> "Clean" -> "Sleep" -> None
// Your code here

Hint

Define a Node struct with task and next. Then build the list from last to first using Some(Box::new(Node { ... })).

2

Create the task to delete variable

Create a variable called task_to_delete and set it to the exact string "Clean".

DSA Rust

struct Node {
    task: String,
    next: Option>,
}

fn main() {
    let head = Some(Box::new(Node {
        task: String::from("Cook"),
        next: Some(Box::new(Node {
            task: String::from("Eat"),
            next: Some(Box::new(Node {
                task: String::from("Clean"),
                next: Some(Box::new(Node {
                    task: String::from("Sleep"),
                    next: None,
                })),
            })),
        })),
    }));

    // Create task_to_delete variable
    // Your code here
}

Hint

Use let task_to_delete = String::from("Clean"); to create the variable.

3

Write the delete_node_by_value function

Write a function called delete_node_by_value that takes head: Option> and value: &str and returns Option>. It should remove the first node whose task equals value and return the new head of the list.

DSA Rust

struct Node {
    task: String,
    next: Option>,
}

fn delete_node_by_value(mut head: Option>, value: &str) -> Option> {
    // Implement deletion logic here
    // Your code here
}

fn main() {
    let head = Some(Box::new(Node {
        task: String::from("Cook"),
        next: Some(Box::new(Node {
            task: String::from("Eat"),
            next: Some(Box::new(Node {
                task: String::from("Clean"),
                next: Some(Box::new(Node {
                    task: String::from("Sleep"),
                    next: None,
                })),
            })),
        })),
    }));

    let task_to_delete = String::from("Clean");

    // Call delete_node_by_value and update head
    // Your code here
}

Hint

Check if the head node matches the value and remove it by returning head.unwrap().next. Otherwise, iterate through nodes and remove the matching next node by changing links.

4

Print the linked list after deletion

Print the tasks in the linked list starting from head after deletion. Use a loop to print each task followed by " -> ". End with null.

DSA Rust

struct Node {
    task: String,
    next: Option>,
}

fn delete_node_by_value(mut head: Option>, value: &str) -> Option> {
    while let Some(ref node) = head {
        if node.task == value {
            return head.unwrap().next;
        } else {
            break;
        }
    }

    let mut current = &mut head;
    while let Some(ref mut node) = current {
        if let Some(ref next_node) = node.next {
            if next_node.task == value {
                node.next = node.next.take().and_then(|n| n.next);
                break;
            }
        }
        current = &mut node.next;
    }
    head
}

fn main() {
    let head = Some(Box::new(Node {
        task: String::from("Cook"),
        next: Some(Box::new(Node {
            task: String::from("Eat"),
            next: Some(Box::new(Node {
                task: String::from("Clean"),
                next: Some(Box::new(Node {
                    task: String::from("Sleep"),
                    next: None,
                })),
            })),
        })),
    }));

    let task_to_delete = String::from("Clean");

    let head = delete_node_by_value(head, &task_to_delete);

    // Print the linked list tasks
    // Your code here
}

Hint

Use a while let loop to traverse the list and print each task followed by " -> ". End with null.

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