Delete from Beginning of Doubly Linked List in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after deleting the first node from a doubly linked list

What is the printed state of the doubly linked list after deleting the first node?

DSA Rust

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

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

#[derive(Debug)]
struct DoublyLinkedList {
    head: Option<Rc<RefCell<Node>>>,
    tail: Option<Rc<RefCell<Node>>>,
}

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

    fn append(&mut self, data: i32) {
        let new_node = Rc::new(RefCell::new(Node { data, prev: None, next: None }));
        match self.tail.take() {
            Some(old_tail) => {
                old_tail.borrow_mut().next = Some(new_node.clone());
                new_node.borrow_mut().prev = Some(old_tail);
                self.tail = Some(new_node);
            }
            None => {
                self.head = Some(new_node.clone());
                self.tail = Some(new_node);
            }
        }
    }

    fn delete_from_beginning(&mut self) {
        if let Some(old_head) = self.head.take() {
            let next_node = old_head.borrow_mut().next.take();
            match next_node {
                Some(next) => {
                    next.borrow_mut().prev = None;
                    self.head = Some(next);
                }
                None => {
                    self.tail = None;
                }
            }
        }
    }

    fn print_list(&self) {
        let mut current = self.head.clone();
        let mut result = vec![];
        while let Some(node) = current {
            result.push(node.borrow().data);
            current = node.borrow().next.clone();
        }
        let output = result.iter().map(|d| d.to_string()).collect::<Vec<_>>().join(" <-> ");
        println!("{} <-> null", output);
    }
}

fn main() {
    let mut dll = DoublyLinkedList::new();
    dll.append(10);
    dll.append(20);
    dll.append(30);
    dll.delete_from_beginning();
    dll.print_list();
}

A 30 <-> null

B 10 <-> 20 <-> 30 <-> null

C 20 <-> 30 <-> null

D null

💡 Hint

Deleting from the beginning removes the first node and updates the head pointer.

The list initially is 10 <-> 20 <-> 30 <-> null. After deleting the first node (10), the new head is 20, so the list becomes 20 <-> 30 <-> null.

❓ Predict Output

intermediate

Output after deleting from an empty doubly linked list

What is the printed state of the doubly linked list after attempting to delete from an empty list?

DSA Rust

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

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

#[derive(Debug)]
struct DoublyLinkedList {
    head: Option<Rc<RefCell<Node>>>,
    tail: Option<Rc<RefCell<Node>>>,
}

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

    fn delete_from_beginning(&mut self) {
        if let Some(old_head) = self.head.take() {
            let next_node = old_head.borrow_mut().next.take();
            match next_node {
                Some(next) => {
                    next.borrow_mut().prev = None;
                    self.head = Some(next);
                }
                None => {
                    self.tail = None;
                }
            }
        }
    }

    fn print_list(&self) {
        let mut current = self.head.clone();
        let mut result = vec![];
        while let Some(node) = current {
            result.push(node.borrow().data);
            current = node.borrow().next.clone();
        }
        if result.is_empty() {
            println!("null");
        } else {
            let output = result.iter().map(|d| d.to_string()).collect::<Vec<_>>().join(" <-> ");
            println!("{} <-> null", output);
        }
    }
}

fn main() {
    let mut dll = DoublyLinkedList::new();
    dll.delete_from_beginning();
    dll.print_list();
}

A 0 <-> null

B empty list

C panic: called `Option::unwrap()` on a `None` value

D null

💡 Hint

Deleting from an empty list should not crash and the list remains empty.

Since the list is empty, deleting from the beginning does nothing. The printed output is 'null' indicating an empty list.

🔧 Debug

advanced

Identify the error in deleting the first node from a doubly linked list

What error will this code produce when deleting the first node?

DSA Rust

struct Node {
    data: i32,
    prev: Option<Box<Node>>,
    next: Option<Box<Node>>,
}

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

impl DoublyLinkedList {
    fn delete_from_beginning(&mut self) {
        if let Some(mut old_head) = self.head.take() {
            self.head = old_head.next.take();
            if let Some(ref mut new_head) = self.head {
                new_head.prev = None;
            } else {
                self.tail = None;
            }
        }
    }
}

fn main() {
    let mut dll = DoublyLinkedList { head: None, tail: None };
    dll.delete_from_beginning();
}

A Runtime panic due to use of moved value 'old_head'

B Compilation error: cannot assign None to new_head.prev because prev is Option<Box<Node>> but expected Option<Rc<RefCell<Node>>>

C No error, code runs fine

D Compilation error: cannot assign None to new_head.prev because prev is not Option<Box<Node>>

💡 Hint

Check ownership and move semantics when taking old_head and accessing next.

The code moves old_head out of self.head, then tries to access old_head.next after move, causing use of moved value error.

❓ Predict Output

advanced

Output after multiple deletions from beginning of doubly linked list

What is the printed state of the doubly linked list after deleting the first node twice?

DSA Rust

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

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

#[derive(Debug)]
struct DoublyLinkedList {
    head: Option<Rc<RefCell<Node>>>,
    tail: Option<Rc<RefCell<Node>>>,
}

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

    fn append(&mut self, data: i32) {
        let new_node = Rc::new(RefCell::new(Node { data, prev: None, next: None }));
        match self.tail.take() {
            Some(old_tail) => {
                old_tail.borrow_mut().next = Some(new_node.clone());
                new_node.borrow_mut().prev = Some(old_tail);
                self.tail = Some(new_node);
            }
            None => {
                self.head = Some(new_node.clone());
                self.tail = Some(new_node);
            }
        }
    }

    fn delete_from_beginning(&mut self) {
        if let Some(old_head) = self.head.take() {
            let next_node = old_head.borrow_mut().next.take();
            match next_node {
                Some(next) => {
                    next.borrow_mut().prev = None;
                    self.head = Some(next);
                }
                None => {
                    self.tail = None;
                }
            }
        }
    }

    fn print_list(&self) {
        let mut current = self.head.clone();
        let mut result = vec![];
        while let Some(node) = current {
            result.push(node.borrow().data);
            current = node.borrow().next.clone();
        }
        if result.is_empty() {
            println!("null");
        } else {
            let output = result.iter().map(|d| d.to_string()).collect::<Vec<_>>().join(" <-> ");
            println!("{} <-> null", output);
        }
    }
}

fn main() {
    let mut dll = DoublyLinkedList::new();
    dll.append(5);
    dll.append(15);
    dll.append(25);
    dll.delete_from_beginning();
    dll.delete_from_beginning();
    dll.print_list();
}

A 5 <-> 15 <-> 25 <-> null

B 25 <-> null

C 15 <-> 25 <-> null

D null

💡 Hint

Each deletion removes the current head node and updates the head pointer.

After first deletion, list is 15 <-> 25 <-> null. After second deletion, list is 25 <-> null.

🧠 Conceptual

expert

Why is it important to update the 'prev' pointer of the new head when deleting from the beginning?

In a doubly linked list, after deleting the first node, why must the 'prev' pointer of the new head be set to None?

A To avoid memory leaks by breaking the backward link to the deleted node

B Because the 'prev' pointer must always point to the tail node

C To keep the list circular and connected

D Because the 'prev' pointer is not used in doubly linked lists

💡 Hint

Think about how nodes are connected backward and what happens if the old head is removed.

Setting the 'prev' pointer of the new head to None removes the backward link to the deleted node, preventing dangling references and potential memory leaks.

Practice

1. What happens to the head pointer when you delete the first node from a doubly linked list?

easy

A. It points to the last node

B. It moves to the next node in the list

C. It becomes null immediately

D. It remains unchanged

Solution

1. Step 1: Understand the role of head in a doubly linked list

   The head pointer always points to the first node in the list.

2. Step 2: Effect of deleting the first node

   When the first node is deleted, the head must move to the next node to keep the list accessible.

3. Final Answer:

   It moves to the next node in the list -> Option B

4. Quick Check:

   Deleting first node updates head to next node [OK]

Hint: Head always points to first node; update it after deletion [OK]

Common Mistakes:

• Not updating head pointer after deletion
• Setting head to null without checking list length
• Confusing head with tail pointer

2. Which of the following Rust code snippets correctly deletes the first node from a doubly linked list?

easy

A. if let Some(mut node) = head.take() { head = node.next.take(); if let Some(ref mut new_head) = head { new_head.prev = None; } }

B. head = head.next; head.prev = None;

C. head = None; tail = None;

D. head.prev = None; head = head.next;

Solution

1. Step 1: Analyze safe Rust deletion pattern

   if let Some(mut node) = head.take() { head = node.next.take(); if let Some(ref mut new_head) = head { new_head.prev = None; } } uses take() to safely remove the first node and updates head and prev pointers correctly.

2. Step 2: Check other options for errors

   head = head.next; head.prev = None; tries to access head.next without handling Option. head = None; tail = None; deletes entire list incorrectly. head.prev = None; head = head.next; accesses head.prev before updating head, causing error.

3. Final Answer:

   Option A code snippet -> Option A

4. Quick Check:

   Safe pointer update with take() = if let Some(mut node) = head.take() { head = node.next.take(); if let Some(ref mut new_head) = head { new_head.prev = None; } } [OK]

Hint: Use take() to safely remove and update pointers [OK]

Common Mistakes:

• Ignoring Option unwrap safety
• Not updating prev pointer of new head
• Setting head to None without checking

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

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

// List: 10 <-> 20 <-> 30
let mut head = Some(Box::new(Node { val: 10, prev: None, next: Some(Box::new(Node { val: 20, prev: None, next: Some(Box::new(Node { val: 30, prev: None, next: None })) })) }));

// Delete first node
if let Some(mut node) = head.take() {
  head = node.next.take();
  if let Some(ref mut new_head) = head {
    new_head.prev = None;
  }
}

// Print list
let mut current = &head;
while let Some(node) = current {
  print!("{} -> ", node.val);
  current = &node.next;
}
print!("null");

medium

A. null

B. 10 -> 20 -> 30 -> null

C. 20 -> 30 -> null

D. 30 -> null

Solution

1. Step 1: Initial list structure

   The list starts as 10 <-> 20 <-> 30, with head at 10.

2. Step 2: Deletion of first node

   Deleting first node moves head to 20, and sets 20.prev to None.

3. Step 3: Printing the list

   Starting from new head (20), printing nodes gives 20 -> 30 -> null.

4. Final Answer:

   20 -> 30 -> null -> Option C

5. Quick Check:

   Head updated to second node, list prints from 20 [OK]

Hint: After deletion, head points to second node; print from there [OK]

Common Mistakes:

• Printing old head after deletion
• Not updating prev pointer causing broken links
• Confusing next and prev pointers

4. Identify the error in this Rust code snippet that tries to delete the first node from a doubly linked list:

if head.is_some() {
  head = head.unwrap().next;
  if let Some(ref mut new_head) = head {
    new_head.prev = None;
  }
}

medium

A. Using unwrap() consumes head, causing a move error

B. Not setting new_head.prev to None

C. Missing check if head is None before deletion

D. Incorrectly updating tail pointer

Solution

1. Step 1: Understand unwrap() behavior on Option

   Calling unwrap() on head moves the value out, consuming it and invalidating head.

2. Step 2: Consequence of move error

   Assigning head = head.unwrap().next; causes a move error because head is used after being moved.

3. Final Answer:

   Using unwrap() consumes head, causing a move error -> Option A

4. Quick Check:

   unwrap() moves value, invalidating head [OK]

Hint: Avoid unwrap() on Option when reassigning; use take() [OK]

Common Mistakes:

• Using unwrap() causing move errors
• Not handling Option safely
• Forgetting to update prev pointer

5. You have a doubly linked list with nodes: 5 <-> 15 <-> 25 <-> 35. After deleting the first node twice using correct Rust code, what will be the final list printed?

let mut head = Some(Box::new(Node { val: 5, prev: None, next: Some(Box::new(Node { val: 15, prev: None, next: Some(Box::new(Node { val: 25, prev: None, next: Some(Box::new(Node { val: 35, prev: None, next: None })) })) })) }));

// Delete first node twice
for _ in 0..2 {
  if let Some(mut node) = head.take() {
    head = node.next.take();
    if let Some(ref mut new_head) = head {
      new_head.prev = None;
    }
  }
}

// Print list
let mut current = &head;
while let Some(node) = current {
  print!("{} -> ", node.val);
  current = &node.next;
}
print!("null");

hard

A. 15 -> 25 -> 35 -> null

B. null

C. 35 -> null

D. 25 -> 35 -> null

Solution

1. Step 1: Initial list and first deletion

   List starts as 5 <-> 15 <-> 25 <-> 35. First deletion removes 5, head moves to 15.

2. Step 2: Second deletion

   Second deletion removes 15, head moves to 25, and 25.prev is set to None.

3. Step 3: Printing final list

   Starting from 25, printing nodes gives 25 -> 35 -> null.

4. Final Answer:

   25 -> 35 -> null -> Option D

5. Quick Check:

   Two deletions move head twice forward [OK]

Hint: Each deletion moves head to next node; repeat for multiple deletions [OK]

Common Mistakes:

• Not updating prev pointer after each deletion
• Deleting only once instead of twice
• Printing old head after deletions