Delete from End of Doubly Linked List in DSA Python - 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 None

No↓

Move tail pointer to previous node

↓

Set new tail's next to None

↓

Delete old tail node

↓

Done

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

Execution Sample

DSA Python

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def delete_end(self):
        if not self.tail:
            return
        if self.head == self.tail:
            self.head = None
            self.tail = None
            return
        self.tail = self.tail.prev
        self.tail.next = None

Deletes the last node from a doubly linked list, updating pointers accordingly.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with list: 10 <-> 20 <-> 30 <-> 40	10 <-> 20 <-> 30 <-> 40	head → 10, tail → 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 previous node (30)	10 <-> 20 <-> 30 <-> 40	tail: 40 → 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 here)
5	Set new tail's next to None	10 <-> 20 <-> 30	30.next: 40 → None	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ prev:∅ │←── │ prev:10│←── │ prev:20│ │ next:20│──→ │ next:30│──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head tail
6	Old tail (40) is now disconnected and deleted	10 <-> 20 <-> 30	40 node removed	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ prev:∅ │←── │ prev:10│←── │ prev:20│ │ next:20│──→ │ next:30│──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head tail
7	End of delete operation	10 <-> 20 <-> 30	Pointers stable	Same as step 6

💡 Tail moved to previous node and old tail disconnected, list updated

Variable Tracker

Variable	Start	After Step 4	After Step 5	Final
head	Node(10)	Node(10)	Node(10)	Node(10)
tail	Node(40)	Node(30)	Node(30)	Node(30)
tail.next	None	Node(40)	None	None
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. We must set both head and tail to None to avoid dangling pointers. See step 3 in execution_table.

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

Because the new tail is the last node now, so its next pointer must not point to any node. This disconnects the old tail. See step 5 in execution_table.

What happens to the old tail node after deletion?

It becomes disconnected from the list and is removed from memory (garbage collected). It no longer has any references. See step 6 in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, which node does the tail pointer move to?

A Node with data 20

B Node with data 30

C Node with data 40

D Node with data 10

💡 Hint

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

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

A Step 3

B Step 6

C Step 5

D Step 7

💡 Hint

Look at the 'Nodes in List' and 'Variable Tracker' after step 5

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

A Both head and tail become None

B Head points to None, tail remains the node

C Both remain pointing to the single node

D Tail points to None, head remains the node

💡 Hint

Refer to step 3 and the key moment 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 None
- Else move tail to tail.prev
- Set new tail.next to None
- Old tail node removed
Pointers updated to keep list consistent

Full Transcript

To delete the last node from a doubly linked list, we start at the tail. If the list is empty, we do nothing. If there is only one node, we set both head and tail to None, making the list empty. Otherwise, we move the tail pointer to the previous node and set the new tail's next pointer to None to disconnect the old tail. The old tail node is then removed from the list. This process updates pointers carefully to maintain the list's structure.

Practice

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

easy

A. The last node is removed and the second last node becomes the new tail.

B. The first node is removed and the second node becomes the new head.

C. All nodes are deleted and the list becomes empty.

D. The middle node is removed and the list remains unchanged at the ends.

Solution

1. Step 1: Identify the last node and update pointers

   In a doubly linked list, the last node is the tail node which has its next pointer as null. Deleting the last node means updating the tail pointer to the previous node and setting its next pointer to null. The second last node becomes the new tail.

2. Final Answer:

   The last node is removed and the second last node becomes the new tail. -> Option A

3. Quick Check:

   Delete end node = tail moves back [OK]

Hint: Last node removed, tail moves to previous node [OK]

Common Mistakes:

• Removing the head instead of the tail
• Not updating the tail pointer
• Leaving the next pointer of new tail non-null

2. Which of the following is the correct syntax to delete the last node in a doubly linked list in Python?

easy

A. head = head.prev; head.next = None

B. tail = tail.next; tail.prev = None

C. head = head.next; head.prev = None

D. tail = tail.prev; tail.next = None

Solution

1. Step 1: Move tail pointer and update next

   To delete the last node, move tail to tail.prev (second last node), then set tail.next to None to mark the end of the list.

2. Final Answer:

   tail = tail.prev; tail.next = None -> Option D

3. Quick Check:

   Correct tail update syntax = tail = tail.prev; tail.next = None [OK]

Hint: Tail moves back, next pointer set to None [OK]

Common Mistakes:

• Moving tail forward instead of backward
• Setting prev pointer instead of next
• Changing head pointer instead of tail

3. What will be the output after deleting the last node from the doubly linked list shown below?

Initial list: 10 <-> 20 <-> 30 <-> 40 <-> None
Operation: Delete from end

What is the resulting list?

medium

A. 10 <-> 20 <-> 30 <-> 40 <-> None

B. 10 <-> 20 <-> 30 <-> None

C. 20 <-> 30 <-> 40 <-> None

D. 10 <-> 20 <-> None

Solution

1. Step 1: Identify last node and update

   The last node is 40, which is removed by setting node 30's next pointer to None, making it the new tail. Result: 10 <-> 20 <-> 30 <-> None.

2. Final Answer:

   10 <-> 20 <-> 30 <-> None -> Option B

3. Quick Check:

   Last node 40 removed, tail is 30 [OK]

Hint: Remove last node, update previous node's next to None [OK]

Common Mistakes:

• Not updating the next pointer of new tail
• Removing the wrong node (head or middle)
• Leaving dangling pointers causing errors

4. Consider the following code snippet to delete the last node from a doubly linked list:

if tail is None:
    print('List is empty')
else:
    tail = tail.prev
    tail.next = None

What error can occur when this code runs on a list with only one node?

medium

A. AttributeError because tail.prev is None and tail.next is accessed

B. No error, code works fine for single node list

C. SyntaxError due to missing colon

D. IndexError because tail is out of range

Solution

1. Step 1: Trace execution for single node

   For one node, tail.prev is None, so tail = None, then tail.next = None accesses None.next causing AttributeError.

2. Final Answer:

   AttributeError because tail.prev is None and tail.next is accessed -> Option A

3. Quick Check:

   Single node delete needs extra check [OK]

Hint: Check if tail.prev is None before setting tail.next [OK]

Common Mistakes:

• Not handling single node list case
• Assuming tail.prev always exists
• Ignoring NoneType attribute errors

5. You have a doubly linked list with nodes: 5 <-> 15 <-> 25 <-> 35 <-> 45 <-> None. You delete the last node twice in a row. What will be the final list?

hard

A. 5 <-> 15 <-> 25 <-> 35 <-> 45 <-> None

B. 5 <-> 15 <-> 25 <-> 35 <-> None

C. 5 <-> 15 <-> 25 <-> None

D. 15 <-> 25 <-> 35 <-> None

Solution

1. Step 1: Perform two deletions

   Initial: 5 <-> 15 <-> 25 <-> 35 <-> 45. First delete removes 45 (tail=35). Second delete removes 35 (tail=25). Final: 5 <-> 15 <-> 25 <-> None.

2. Final Answer:

   5 <-> 15 <-> 25 <-> None -> Option C

3. Quick Check:

   Two deletes remove last two nodes [OK]

Hint: Each delete removes one tail node [OK]

Common Mistakes:

• Deleting only one node instead of two
• Not updating tail pointer after each delete
• Confusing head and tail nodes