Delete from End of Doubly Linked List in DSA Rust - Build from Scratch

Delete from End of Doubly Linked List

📖 Scenario: You are managing a playlist of songs where each song is connected to the previous and next song. You want to remove the last song from the playlist.

🎯 Goal: Build a doubly linked list of songs and write code to delete the last song from the list.

📋 What You'll Learn

Create a doubly linked list with exactly three nodes containing the values 10, 20, and 30 in that order

Create a variable called head that points to the first node

Write code to delete the last node from the doubly linked list

Print the list from head to end showing the values separated by -> and ending with null

💡 Why This Matters

🌍 Real World

Doubly linked lists are used in music players, browsers, and other apps where you need to move forward and backward through items.

💼 Career

Understanding linked lists is important for software developers working with data structures, memory management, and building efficient applications.

1

Create the doubly linked list with three nodes

Create a struct called Node with fields value: i32, prev: *mut Node, and next: *mut Node. Then create three nodes with values 10, 20, and 30 linked as a doubly linked list. Create a variable called head that points to the first node with value 10.

DSA Rust

// Define struct Node and create the doubly linked list with head pointing to value 10
// Your code here

Hint

Define the Node struct with value, prev: *mut Node, and next: *mut Node. Use Box::into_raw to get raw pointers, link them bidirectionally in an unsafe block, and assign the first node pointer to head.

2

Add a helper variable to track the current node

Create a mutable variable called current and set it equal to head to start traversing from the head node.

DSA Rust

use std::ptr::null_mut;

struct Node {
    value: i32,
    prev: *mut Node,
    next: *mut Node,
}

fn main() {
    let node1_box = Box::new(Node { value: 10, prev: null_mut(), next: null_mut() });
    let head: *mut Node = Box::into_raw(node1_box);
    let node2_box = Box::new(Node { value: 20, prev: head, next: null_mut() });
    let node2: *mut Node = Box::into_raw(node2_box);
    let node3_box = Box::new(Node { value: 30, prev: node2, next: null_mut() });
    let node3: *mut Node = Box::into_raw(node3_box);
    unsafe {
        (*head).next = node2;
        (*node2).prev = head;
        (*node2).next = node3;
        (*node3).prev = node2;
    }
    
    // Create a mutable variable current to start at head
    // Your code here

Hint

Use let mut current = head; to get a mutable raw pointer starting at the head.

3

Delete the last node from the doubly linked list

Use a while loop to move current to the last node by checking unsafe { (*current).next != null_mut() }. Then set the previous node's next to null_mut() to delete the last node.

DSA Rust

use std::ptr::null_mut;

struct Node {
    value: i32,
    prev: *mut Node,
    next: *mut Node,
}

fn main() {
    let node1_box = Box::new(Node { value: 10, prev: null_mut(), next: null_mut() });
    let head: *mut Node = Box::into_raw(node1_box);
    let node2_box = Box::new(Node { value: 20, prev: head, next: null_mut() });
    let node2: *mut Node = Box::into_raw(node2_box);
    let node3_box = Box::new(Node { value: 30, prev: node2, next: null_mut() });
    let node3: *mut Node = Box::into_raw(node3_box);
    unsafe {
        (*head).next = node2;
        (*node2).prev = head;
        (*node2).next = node3;
        (*node3).prev = node2;
    }

    let mut current = head;

    // Move current to last node and delete it by setting previous node's next to null_mut
    // Your code here

Hint

Use a while loop to move current to the last node. Then access the previous node pointer via (*current).prev and set its next to null_mut() to remove the last node.

4

Print the doubly linked list from head to end

Use a while loop to traverse the list starting from head. Print each node's value followed by -> . After the last node, print null.

DSA Rust

use std::ptr::null_mut;

struct Node {
    value: i32,
    prev: *mut Node,
    next: *mut Node,
}

fn main() {
    let node1_box = Box::new(Node { value: 10, prev: null_mut(), next: null_mut() });
    let head: *mut Node = Box::into_raw(node1_box);
    let node2_box = Box::new(Node { value: 20, prev: head, next: null_mut() });
    let node2: *mut Node = Box::into_raw(node2_box);
    let node3_box = Box::new(Node { value: 30, prev: node2, next: null_mut() });
    let node3: *mut Node = Box::into_raw(node3_box);
    unsafe {
        (*head).next = node2;
        (*node2).prev = head;
        (*node2).next = node3;
        (*node3).prev = node2;
    }

    let mut current = head;

    while unsafe { (*current).next != null_mut() } {
        current = unsafe { (*current).next };
    }
    let prev_ptr = unsafe { (*current).prev };
    unsafe { (*prev_ptr).next = null_mut() };

    // Print the list from head to end
    // Your code here

Hint

Start from head and use a while print_node != null_mut() loop with unsafe to print each node's value followed by -> . After the loop, print null.

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