Delete from End of Doubly Linked List in DSA Rust - Execution Trace

Concept Flow - Delete from End of Doubly Linked List

Start at tail node

↓

Check if list is empty?

| No↓

If only one node

| Yes↓

Set head and tail to null

↓

Else

↓

Move tail pointer to tail.prev

↓

Set new tail.next to null

↓

Delete old tail node

↓

Done

Start from the tail node, check if list is empty or has one node, then update pointers to remove the last node.

Execution Sample

DSA Rust

fn delete_from_end(head: &mut Option<*mut Node>, tail: &mut Option<*mut Node>) {
    if tail.is_none() { return; }
    let old_tail = tail.unwrap();
    if unsafe { (*old_tail).prev.is_none() } {
        *head = None;
        *tail = None;
    } else {
        let new_tail = unsafe { (*old_tail).prev.unwrap() };
        unsafe { (*new_tail).next = None; }
        *tail = Some(new_tail);
    }
}

Deletes the last node from a doubly linked list by updating tail and next pointers.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start at tail node (data: 40)	10 <-> 20 <-> 30 <-> 40	tail points to node 40	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ data:40│ │ prev:∅ │←── │ prev:10│←── │ prev:20│←── │ prev:30│ │ next:20│──→ │ next:30│──→ │ next:40│──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ head tail
2	Check if list is empty	10 <-> 20 <-> 30 <-> 40	No change	Same as step 1
3	Check if only one node	10 <-> 20 <-> 30 <-> 40	No change	Same as step 1
4	Move tail pointer to tail.prev (node 30)	10 <-> 20 <-> 30 <-> 40	tail updated to node 30	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ data:40│ │ prev:∅ │←── │ prev:10│←── │ prev:20│←── │ prev:30│ │ next:20│──→ │ next:30│──→ │ next:40│──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ head tail (moved)
5	Set new tail.next to null	10 <-> 20 <-> 30	node 30.next = null	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ prev:∅ │←── │ prev:10│←── │ prev:20│ │ next:20│──→ │ next:30│──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head tail
6	Delete old tail node (40)	10 <-> 20 <-> 30	node 40 removed	Same as step 5
7	Done	10 <-> 20 <-> 30	No change	Final list: 10 <-> 20 <-> 30

💡 Tail updated to previous node and old tail removed, list end node deleted

Variable Tracker

Variable	Start	After Step 4	After Step 5	Final
tail	node 40	node 30	node 30	node 30
tail.next	null	null	null	null
list size	4 nodes	4 nodes	3 nodes	3 nodes

Key Moments - 3 Insights

Why do we check if the list has only one node before deleting?

Because if there is only one node, deleting it means the list becomes empty, so both head and tail must be set to null (see step 3 in execution_table).

Why do we set new tail's next pointer to null?

To mark the new end of the list and avoid dangling references to the deleted node (see step 5 in execution_table).

What happens if the list is empty when delete is called?

The function returns immediately without changes, as tail is None (step 2 in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table, what is the tail pointer after step 4?

A Points to node with data 30

B Points to node with data 40

C Is null

D Points to node with data 20

💡 Hint

Check the 'Pointer Changes' column at step 4 in execution_table

At which step does the list size reduce from 4 to 3 nodes?

A Step 3

B Step 5

C Step 6

D Step 7

💡 Hint

Look at the 'Nodes in List' column in execution_table

If the list had only one node, what would happen to head and tail after deletion?

A Both head and tail become null

B Only tail becomes null

C Only head becomes null

D Neither changes

💡 Hint

Refer to step 3 and the key_moments about single node deletion

Concept Snapshot

Delete from End of Doubly Linked List:
- Start at tail node
- If list empty, do nothing
- If one node, set head and tail to null
- Else move tail to tail.prev
- Set new tail.next to null
- Remove old tail node
- List size decreases by one

Full Transcript

To delete the last node from a doubly linked list, we start at the tail node. If the list is empty, we do nothing. If there is only one node, we set both head and tail to null, making the list empty. Otherwise, we move the tail pointer to the previous node, set the new tail's next pointer to null to mark the end, and remove the old tail node. This reduces the list size by one. The process ensures no dangling pointers remain and the list remains properly linked.

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