Delete Node by Value in DSA Rust - Time & Space Complexity

Time Complexity: Delete Node by Value

O(n)

Understanding Time Complexity

We want to understand how long it takes to remove a node by its value from a linked list.

How does the time needed change as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn delete_node(head: &mut Option>, value: i32) {
    let mut current = head;
    while let Some(ref mut node) = current {
        if node.data == value {
            *current = node.next.take();
            return;
        }
        current = &mut node.next;
    }
}
    

This code searches the linked list for the first node with the given value and removes it.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop through nodes one by one.
• How many times: Up to the number of nodes until the value is found or list ends.

How Execution Grows With Input

As the list grows, the time to find the node grows roughly in a straight line.

Input Size (n)	Approx. Operations
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The number of steps grows directly with the list size.

Final Time Complexity

Time Complexity: O(n)

This means the time to delete a node grows linearly with the number of nodes in the list.

Common Mistake

[X] Wrong: "Deleting a node by value always takes constant time because we just remove it."

[OK] Correct: We must first find the node by checking each one, which can take time proportional to the list size.

Interview Connect

Understanding this helps you explain how searching and modifying linked lists work in real code.

Self-Check

"What if the list was doubly linked? How would the time complexity change?"

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