Delete by Value in Doubly Linked List in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after deleting a middle value from doubly linked list

What is the printed state of the doubly linked list after deleting the value 3?

DSA Rust

struct Node {
    value: i32,
    prev: Option<*mut Node>,
    next: Option<Box<Node>>,
}

struct DoublyLinkedList {
    head: Option<Box<Node>>,
}

impl DoublyLinkedList {
    fn new() -> Self {
        DoublyLinkedList { head: None }
    }

    fn append(&mut self, val: i32) {
        let mut new_node = Box::new(Node { value: val, prev: None, next: None });
        match self.head.as_mut() {
            None => self.head = Some(new_node),
            Some(mut current) => {
                while let Some(ref mut next) = current.next {
                    current = next;
                }
                new_node.prev = Some(&mut **current as *mut Node);
                current.next = Some(new_node);
            }
        }
    }

    fn delete_by_value(&mut self, val: i32) {
        let mut current = self.head.as_mut().map(|node| &mut **node as *mut Node);
        unsafe {
            while let Some(node_ptr) = current {
                let node = &mut *node_ptr;
                if node.value == val {
                    if let Some(prev_ptr) = node.prev {
                        let prev = &mut *prev_ptr;
                        prev.next = node.next.take();
                        if let Some(ref mut next_node) = prev.next {
                            next_node.prev = Some(prev_ptr);
                        }
                    } else {
                        self.head = node.next.take();
                        if let Some(ref mut head_node) = self.head {
                            head_node.prev = None;
                        }
                    }
                    break;
                }
                current = node.next.as_mut().map(|next_node| &mut **next_node as *mut Node);
            }
        }
    }

    fn print_list(&self) {
        let mut current = self.head.as_ref();
        while let Some(node) = current {
            print!("{} -> ", node.value);
            current = node.next.as_ref();
        }
        println!("null");
    }
}

fn main() {
    let mut list = DoublyLinkedList::new();
    list.append(1);
    list.append(2);
    list.append(3);
    list.append(4);
    list.delete_by_value(3);
    list.print_list();
}

A 1 -> 2 -> null

B 1 -> 2 -> 3 -> 4 -> null

C 2 -> 3 -> 4 -> null

D 1 -> 2 -> 4 -> null

💡 Hint

Focus on how the node with value 3 is removed and how links are updated.

The node with value 3 is removed, so the list links 2 directly to 4. The printed list shows 1 -> 2 -> 4 -> null.

❓ Predict Output

intermediate

Output after deleting head value in doubly linked list

What is the printed state of the doubly linked list after deleting the value 1 (head node)?

DSA Rust

struct Node {
    value: i32,
    prev: Option<*mut Node>,
    next: Option<Box<Node>>,
}

struct DoublyLinkedList {
    head: Option<Box<Node>>,
}

impl DoublyLinkedList {
    fn new() -> Self {
        DoublyLinkedList { head: None }
    }

    fn append(&mut self, val: i32) {
        let mut new_node = Box::new(Node { value: val, prev: None, next: None });
        match self.head.as_mut() {
            None => self.head = Some(new_node),
            Some(mut current) => {
                while let Some(ref mut next) = current.next {
                    current = next;
                }
                new_node.prev = Some(&mut **current as *mut Node);
                current.next = Some(new_node);
            }
        }
    }

    fn delete_by_value(&mut self, val: i32) {
        let mut current = self.head.as_mut().map(|node| &mut **node as *mut Node);
        unsafe {
            while let Some(node_ptr) = current {
                let node = &mut *node_ptr;
                if node.value == val {
                    if let Some(prev_ptr) = node.prev {
                        let prev = &mut *prev_ptr;
                        prev.next = node.next.take();
                        if let Some(ref mut next_node) = prev.next {
                            next_node.prev = Some(prev_ptr);
                        }
                    } else {
                        self.head = node.next.take();
                        if let Some(ref mut head_node) = self.head {
                            head_node.prev = None;
                        }
                    }
                    break;
                }
                current = node.next.as_mut().map(|next_node| &mut **next_node as *mut Node);
            }
        }
    }

    fn print_list(&self) {
        let mut current = self.head.as_ref();
        while let Some(node) = current {
            print!("{} -> ", node.value);
            current = node.next.as_ref();
        }
        println!("null");
    }
}

fn main() {
    let mut list = DoublyLinkedList::new();
    list.append(1);
    list.append(2);
    list.append(3);
    list.append(4);
    list.delete_by_value(1);
    list.print_list();
}

A 2 -> 3 -> 4 -> null

B 1 -> 3 -> 4 -> null

C 1 -> 2 -> 3 -> 4 -> null

D null

💡 Hint

Deleting the head means the next node becomes the new head.

After deleting the head node with value 1, the new head is the node with value 2. The list prints 2 -> 3 -> 4 -> null.

🔧 Debug

advanced

Identify the bug causing incorrect deletion in doubly linked list

Given the delete_by_value function below, what is the bug that causes the list to become corrupted after deleting a node?

DSA Rust

fn delete_by_value(&mut self, val: i32) {
    let mut current = self.head.as_mut();
    while let Some(node) = current {
        if node.value == val {
            if let Some(prev) = node.prev.as_mut() {
                prev.next = node.next.take();
            } else {
                self.head = node.next.take();
            }
            break;
        }
        current = node.next.as_mut();
    }
}

A The function uses a mutable reference incorrectly causing a compile error.

B The function does not update the prev pointer of the next node after deletion.

C The function incorrectly deletes the head node always.

D The function does not check if the list is empty before deletion.

💡 Hint

Think about the links on both sides of the deleted node.

After removing the node, the next node's prev pointer must be updated to point to the previous node. Missing this causes list corruption.

❓ Predict Output

advanced

Output after deleting a non-existent value in doubly linked list

What is the printed state of the doubly linked list after attempting to delete the value 5 which does not exist in the list?

DSA Rust

struct Node {
    value: i32,
    prev: Option<*mut Node>,
    next: Option<Box<Node>>,
}

struct DoublyLinkedList {
    head: Option<Box<Node>>,
}

impl DoublyLinkedList {
    fn new() -> Self {
        DoublyLinkedList { head: None }
    }

    fn append(&mut self, val: i32) {
        let mut new_node = Box::new(Node { value: val, prev: None, next: None });
        match self.head.as_mut() {
            None => self.head = Some(new_node),
            Some(mut current) => {
                while let Some(ref mut next) = current.next {
                    current = next;
                }
                new_node.prev = Some(&mut **current as *mut Node);
                current.next = Some(new_node);
            }
        }
    }

    fn delete_by_value(&mut self, val: i32) {
        let mut current = self.head.as_mut().map(|node| &mut **node as *mut Node);
        unsafe {
            while let Some(node_ptr) = current {
                let node = &mut *node_ptr;
                if node.value == val {
                    if let Some(prev_ptr) = node.prev {
                        let prev = &mut *prev_ptr;
                        prev.next = node.next.take();
                        if let Some(ref mut next_node) = prev.next {
                            next_node.prev = Some(prev_ptr);
                        }
                    } else {
                        self.head = node.next.take();
                        if let Some(ref mut head_node) = self.head {
                            head_node.prev = None;
                        }
                    }
                    break;
                }
                current = node.next.as_mut().map(|next_node| &mut **next_node as *mut Node);
            }
        }
    }

    fn print_list(&self) {
        let mut current = self.head.as_ref();
        while let Some(node) = current {
            print!("{} -> ", node.value);
            current = node.next.as_ref();
        }
        println!("null");
    }
}

fn main() {
    let mut list = DoublyLinkedList::new();
    list.append(1);
    list.append(2);
    list.append(3);
    list.append(4);
    list.delete_by_value(5);
    list.print_list();
}

A 1 -> 2 -> 3 -> 4 -> null

B null

C 2 -> 3 -> 4 -> null

D 1 -> 2 -> 4 -> null

💡 Hint

Deleting a value not in the list should not change the list.

Since value 5 is not found, the list remains unchanged and prints 1 -> 2 -> 3 -> 4 -> null.

❓ Predict Output

expert

Output after deleting all occurrences of a value in doubly linked list

What is the printed state of the doubly linked list after deleting all nodes with value 2?

DSA Rust

struct Node {
    value: i32,
    prev: Option<*mut Node>,
    next: Option<Box<Node>>,
}

struct DoublyLinkedList {
    head: Option<Box<Node>>,
}

impl DoublyLinkedList {
    fn new() -> Self {
        DoublyLinkedList { head: None }
    }

    fn append(&mut self, val: i32) {
        let mut new_node = Box::new(Node { value: val, prev: None, next: None });
        match self.head.as_mut() {
            None => self.head = Some(new_node),
            Some(mut current) => {
                while let Some(ref mut next) = current.next {
                    current = next;
                }
                new_node.prev = Some(&mut **current as *mut Node);
                current.next = Some(new_node);
            }
        }
    }

    fn delete_all_by_value(&mut self, val: i32) {
        let mut current = self.head.as_mut().map(|node| &mut **node as *mut Node);
        unsafe {
            while let Some(node_ptr) = current {
                let node = &mut *node_ptr;
                if node.value == val {
                    if let Some(prev_ptr) = node.prev {
                        let prev = &mut *prev_ptr;
                        prev.next = node.next.take();
                        if let Some(ref mut next_node) = prev.next {
                            next_node.prev = Some(prev_ptr);
                        }
                        current = prev.next.as_mut().map(|next_node| &mut **next_node as *mut Node);
                    } else {
                        self.head = node.next.take();
                        if let Some(ref mut head_node) = self.head {
                            head_node.prev = None;
                        }
                        current = self.head.as_mut().map(|node| &mut **node as *mut Node);
                    }
                } else {
                    current = node.next.as_mut().map(|next_node| &mut **next_node as *mut Node);
                }
            }
        }
    }

    fn print_list(&self) {
        let mut current = self.head.as_ref();
        while let Some(node) = current {
            print!("{} -> ", node.value);
            current = node.next.as_ref();
        }
        println!("null");
    }
}

fn main() {
    let mut list = DoublyLinkedList::new();
    list.append(1);
    list.append(2);
    list.append(3);
    list.append(2);
    list.append(4);
    list.delete_all_by_value(2);
    list.print_list();
}

A 1 -> 2 -> 3 -> 4 -> null

B 3 -> 4 -> null

C 1 -> 3 -> 4 -> null

D 1 -> 3 -> 2 -> 4 -> null

💡 Hint

All nodes with value 2 should be removed, including multiple occurrences.

Both nodes with value 2 are deleted, leaving 1 -> 3 -> 4 -> null.

Practice

1. What is the main purpose of the delete_by_value function in a doubly linked list?

easy

A. To remove the first node that contains the given value

B. To add a new node with the given value at the end

C. To reverse the entire doubly linked list

D. To count how many nodes have the given value

Solution

1. Step 1: Understand the function's goal

   The delete_by_value function searches for a node with the specified value.

2. Step 2: Identify the action performed

   Once found, it removes that node from the doubly linked list, adjusting pointers accordingly.

3. Final Answer:

   To remove the first node that contains the given value -> Option A

4. Quick Check:

   Delete by value means remove matching node [OK]

Hint: Delete by value removes first matching node [OK]

Common Mistakes:

• Confusing delete with insert
• Thinking it reverses the list
• Assuming it counts nodes

2. Which Rust syntax correctly declares a mutable doubly linked list node struct with prev and next pointers?

easy

A. struct Node { value: i32, prev: Option>, next: Option> }

B. struct Node { value: i32, prev: Option<*mut Node>, next: Option<*mut Node> }

C. struct Node { value: i32, prev: Option, next: Option }

D. struct Node { value: i32, prev: Option<Node>, next: Option<Node> }

Solution

1. Step 1: Understand Rust pointer types for doubly linked lists

   Rust needs shared ownership and mutability for prev and next pointers, so Rc is used.

2. Step 2: Check options for correct pointer usage

   struct Node { value: i32, prev: Option>, next: Option> } uses Option> which allows multiple owners and interior mutability, suitable for doubly linked lists.

3. Final Answer:

   struct Node { value: i32, prev: Option>, next: Option> } -> Option A

4. Quick Check:

   Use Rc and RefCell for mutable shared nodes [OK]

Hint: Use Rc for mutable shared pointers [OK]

Common Mistakes:

• Using Box for both prev and next causes ownership issues
• Using raw pointers without unsafe code
• Using direct Node type causing infinite size

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

let mut list = DoublyLinkedList::new();
list.push_back(1);
list.push_back(3);
list.push_back(5);
list.delete_by_value(3);
list.print();

medium

A. 1 -> 3 -> 5 -> null

B. 1 -> 5 -> null

C. 3 -> 5 -> null

D. 1 -> null

Solution

1. Step 1: Understand initial list state

   After pushing 1, 3, 5, the list is 1 -> 3 -> 5 -> null.

2. Step 2: Delete node with value 3

   The delete_by_value(3) removes the node containing 3, linking 1 directly to 5.

3. Final Answer:

   1 -> 5 -> null -> Option B

4. Quick Check:

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

Hint: Deleting value removes that node, links neighbors [OK]

Common Mistakes:

• Not updating prev and next pointers correctly
• Deleting wrong node or none
• Printing old list without deletion

4. Consider this Rust function snippet for deleting a node by value in a doubly linked list:

fn delete_by_value(&mut self, val: i32) {
    let mut current = self.head.clone();
    while let Some(node) = current {
        if node.borrow().value == val {
            // deletion logic here
            break;
        }
        current = node.borrow().next.clone();
    }
}

What is a common bug if the deletion logic forgets to update the prev pointer of the next node?

medium

A. The list will reverse automatically

B. The head pointer will always point to null

C. The deleted node will remain in memory forever

D. The list may become corrupted with dangling backward links

Solution

1. Step 1: Identify pointer updates needed on deletion

   When deleting a node, the previous node's next and the next node's prev pointers must be updated to bypass the deleted node.

2. Step 2: Consequence of missing prev update

   If the next node's prev pointer is not updated, it still points to the deleted node, causing backward links to be incorrect and list corruption.

3. Final Answer:

   The list may become corrupted with dangling backward links -> Option D

4. Quick Check:

   Missing prev update breaks backward links [OK]

Hint: Always update both prev and next pointers when deleting [OK]

Common Mistakes:

• Updating only next pointer
• Not breaking loop after deletion
• Forgetting to handle head or tail cases

5. You have a doubly linked list with nodes: 2 -> 4 -> 6 -> 4 -> 8 -> null. You want to delete all nodes with value 4 using a delete_by_value function that removes only the first matching node per call. How many times must you call delete_by_value(4) to remove all 4s, and what will the final list look like?

hard

A. Call once; final list: 2 -> 4 -> 6 -> 8 -> null

B. Call once; final list: 2 -> 6 -> 4 -> 8 -> null

C. Call twice; final list: 2 -> 6 -> 8 -> null

D. Call twice; final list: 2 -> 4 -> 6 -> 8 -> null

Solution

1. Step 1: Understand deletion per call

   Each call to delete_by_value(4) removes only the first node with value 4.

2. Step 2: Count how many 4s and calls needed

   There are two nodes with value 4. So, two calls are needed to remove both.

3. Step 3: Final list after deletions

   After two deletions, the list becomes 2 -> 6 -> 8 -> null.

4. Final Answer:

   Call twice; final list: 2 -> 6 -> 8 -> null -> Option C

5. Quick Check:

   Two 4s, two deletes, final list without 4s [OK]

Hint: Delete one node per call; repeat to remove all matches [OK]

Common Mistakes:

• Assuming one call removes all matching nodes
• Not updating pointers after each deletion
• Confusing node values or order