Delete from End of Doubly Linked List in DSA Rust

Mental Model

To remove the last item, we find the tail and unlink it from the list, updating the previous node to be the new tail.

Analogy: Imagine a train of connected cars. To remove the last car, you detach it from the one before it, making the second last car the new end.

head -> 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5 ← tail
null ← 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5 -> null

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5, delete from end

Goal: Remove the last node (5) and update the list tail to node 4

Step 1: start at head, move to tail node 5

1 ↔ 2 ↔ 3 ↔ 4 ↔ [5↑]

Why: We need to find the last node to remove it

Step 2: unlink node 5 by setting node 4's next to null

1 ↔ 2 ↔ 3 ↔ 4 -> null, 5 (removed)

Why: Removing last node means previous node's next must be null

Step 3: update tail pointer to node 4

head -> 1 ↔ 2 ↔ 3 ↔ [4↑] ← tail
null ← 1 ↔ 2 ↔ 3 ↔ 4 -> null

Why: Tail must point to new last node after deletion

Result:

1 ↔ 2 ↔ 3 ↔ 4 -> null

Annotated Code

DSA Rust

use std::rc::{Rc, Weak};
use std::cell::RefCell;

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

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

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, val: i32) {
        let new_node = Node::new(val);
        match self.tail.take() {
            Some(old_tail) => {
                old_tail.borrow_mut().next = Some(new_node.clone());
                new_node.borrow_mut().prev = Some(Rc::downgrade(&old_tail));
                self.tail = Some(new_node);
            }
            None => {
                self.head = Some(new_node.clone());
                self.tail = Some(new_node);
            }
        }
    }

    fn delete_from_end(&mut self) {
        match self.tail.take() {
            None => return, // empty list, nothing to delete
            Some(old_tail) => {
                let prev = old_tail.borrow_mut().prev.take();
                match prev {
                    Some(weak_prev) => {
                        if let Some(prev_rc) = weak_prev.upgrade() {
                            prev_rc.borrow_mut().next = None; // unlink last node
                            self.tail = Some(prev_rc); // update tail
                        }
                    }
                    None => {
                        // only one node in list
                        self.head = None;
                        self.tail = None;
                    }
                }
            }
        }
    }

    fn print_list(&self) {
        let mut curr = self.head.clone();
        while let Some(node) = curr {
            print!("{}", node.borrow().val);
            curr = node.borrow().next.clone();
            if curr.is_some() {
                print!(" ↔ ");
            }
        }
        println!(" -> null");
    }
}

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

match self.tail.take() {

check if list is empty or get current tail to delete

let prev = old_tail.borrow_mut().prev.take();

get previous node of tail to update links

prev_rc.borrow_mut().next = None; // unlink last node

remove last node by setting previous node's next to null

self.tail = Some(prev_rc); // update tail

update tail pointer to new last node

self.head = None; self.tail = None;

handle case when list had only one node, now empty

Output

1 ↔ 2 ↔ 3 ↔ 4 -> null

Complexity Analysis

Time: O(1) because we directly access the tail and update pointers without traversal

Space: O(1) as no extra space is used besides a few pointers

vs Alternative: Compared to singly linked list where deleting last node requires traversal O(n), doubly linked list allows O(1) deletion from end

Edge Cases

empty list

delete_from_end does nothing, list remains empty

DSA Rust

match self.tail.take() { None => return, ... }

single node list

deleting last node empties the list, head and tail become None

DSA Rust

None => { self.head = None; self.tail = None; }

When to Use This Pattern

When you need to remove the last element quickly from a list, use a doubly linked list because it keeps a tail pointer and backward links for O(1) deletion.

Common Mistakes

Mistake: Not updating the tail pointer after deletion, leaving it pointing to a removed node
Fix: Always update the tail pointer to the previous node or None if list is empty

Mistake: Not handling the single node case, causing head to remain pointing to deleted node
Fix: Check if previous node exists; if not, set head and tail to None

Summary

Deletes the last node from a doubly linked list by unlinking it and updating the tail.

Use when you want efficient removal from the end of a list without traversal.

The key is to use the tail pointer and previous links to remove the last node in O(1) time.

Practice

1. What happens when you delete the last node from a doubly linked list that has multiple nodes?

easy

A. The second last node becomes the new tail and its next pointer is set to null

B. The head pointer is set to null

C. The list becomes circular

D. The first node is deleted instead

Solution

1. Step 1: Understand the tail node removal

   When deleting the last node, the node before it becomes the new tail.

2. Step 2: Update pointers

   The new tail's next pointer must be set to null to mark the end of the list.

3. Final Answer:

   The second last node becomes the new tail and its next pointer is set to null -> Option A

4. Quick Check:

   Tail update = new tail with next = null [OK]

Hint: Last node removal means update tail and set next to null [OK]

Common Mistakes:

• Not updating the tail pointer
• Forgetting to set next pointer of new tail to null
• Deleting the head instead of the tail

2. Which Rust code snippet correctly deletes the last node from a doubly linked list?

easy

A. if let Some(tail) = self.tail.take() { if let Some(prev) = tail.prev.take() { prev.next = null; self.tail = Some(prev); } else { self.head = null; } }

B. self.head = null; self.tail = null;

C. self.tail = self.tail.unwrap().prev;

D. self.tail = null; self.head = null;

Solution

1. Step 1: Check tail existence and update pointers

   The code safely takes the tail node, then updates the previous node's next pointer to null.

2. Step 2: Update tail or head accordingly

   If previous node exists, tail is updated to it; else, list becomes empty by setting head to null.

3. Final Answer:

   Code snippet that safely updates tail and head pointers -> Option A

4. Quick Check:

   Safe pointer update with if let Some(tail) = self.tail.take() { if let Some(prev) = tail.prev.take() { prev.next = null; self.tail = Some(prev); } else { self.head = null; } } [OK]

Hint: Use take() and update prev.next and tail safely [OK]

Common Mistakes:

• Directly assigning tail without checking Option
• Not updating previous node's next pointer
• Setting head to null without checking list length

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

let mut list = DoublyLinkedList::new();
list.push_back(1);
list.push_back(2);
list.push_back(3);
list.delete_from_end();
list.print();

medium

A. 1 -> 2 -> 3 -> null

B. 1 -> 2 -> null

C. 2 -> 3 -> null

D. null

Solution

1. Step 1: Initial list state

   The list contains nodes 1, 2, 3 in order.

2. Step 2: Delete last node

   Deleting from end removes node 3, so list becomes 1 -> 2.

3. Final Answer:

   1 -> 2 -> null -> Option B

4. Quick Check:

   After deletion, last node removed = 1 -> 2 [OK]

Hint: Deleting end removes last node only [OK]

Common Mistakes:

• Assuming head node is deleted
• Not updating tail pointer
• Printing old list without deletion

4. Identify the bug in this Rust function that deletes the last node from a doubly linked list:

fn delete_from_end(&mut self) {
    if self.tail.is_none() {
        return;
    }
    let tail = self.tail.unwrap();
    if let Some(prev) = tail.prev {
        prev.next = null;
        self.tail = Some(prev);
    } else {
        self.head = null;
        self.tail = null;
    }
}

medium

A. prev.next is not set to null

B. Not updating head pointer when list has multiple nodes

C. Using unwrap() on Option without safe handling causes panic

D. Function does not check if list is empty

Solution

1. Step 1: Analyze unwrap() usage

   Calling unwrap() on tail without checking can panic if tail is null.

2. Step 2: Suggest safe handling

   Use if let or take() to safely handle Option values without panic.

3. Final Answer:

   Using unwrap() on Option without safe handling causes panic -> Option C

4. Quick Check:

   Unsafe unwrap() = panic risk [OK]

Hint: Avoid unwrap() on Option; use safe pattern matching [OK]

Common Mistakes:

• Ignoring Option safety and causing runtime panic
• Not updating tail pointer after deletion
• Forgetting to set prev.next to null

5. You have a doubly linked list with nodes containing values [10, 20, 30]. After deleting the last node twice, what will be the state of the list?

hard

A. 10 -> 20 -> null

B. null

C. 20 -> 30 -> null

D. 10 -> null

Solution

1. Step 1: Initial list nodes

   The list starts as 10 -> 20 -> 30.

2. Step 2: Delete last node once

   Removing last node 30 results in 10 -> 20.

3. Step 3: Delete last node again

   Removing last node 20 results in 10.

4. Final Answer:

   10 -> null -> Option D

5. Quick Check:

   Two deletions remove last two nodes [OK]

Hint: Each delete removes last node, update tail and next [OK]

Common Mistakes:

• Deleting head instead of tail
• Not updating tail after each deletion
• Assuming list becomes empty too early