Delete from End of Doubly Linked List in DSA Python

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 carriages. To remove the last carriage, you detach it from the one before it, so the second last becomes the new end.

head -> 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5 ← tail
Each arrow ↔ shows two-way links between nodes.

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: Access tail directly (O(1) since tail pointer maintained)

head -> 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5 ↑tail

Why: Tail pointer gives direct access to last node

Step 2: Capture deleted_data = tail.data # 5

head -> 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5 ↑tail

Why: Save data before unlinking node

Step 3: tail = tail.prev # move tail to node 4

head -> 1 ↔ 2 ↔ 3 ↔ 4 ↑tail  5

Why: Update tail to point to new last node

Step 4: tail.next = None # unlink old tail (5)

head -> 1 ↔ 2 ↔ 3 ↔ 4 ↑tail
5 is removed

Why: Sever forward link to fully remove node

Result:

head -> 1 ↔ 2 ↔ 3 ↔ 4 ← tail
Deleted node: 5

Annotated Code

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 append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.tail = new_node
            return
        self.tail.next = new_node
        new_node.prev = self.tail
        self.tail = new_node

    def delete_from_end(self):
        if not self.tail:  # empty list
            return None
        deleted_data = self.tail.data
        if self.head == self.tail:  # single node
            self.head = None
            self.tail = None
            return deleted_data
        # unlink last node
        self.tail = self.tail.prev
        self.tail.next = None
        return deleted_data

    def __str__(self):
        nodes = []
        curr = self.head
        while curr:
            nodes.append(str(curr.data))
            curr = curr.next
        return ' ↔ '.join(nodes) + ' ← tail'

# Driver code
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.append(4)
dll.append(5)
print("Before deletion:", dll)
deleted = dll.delete_from_end()
print(f"Deleted node: {deleted}")
print("After deletion:", dll)

if not self.tail: # empty list

check if list is empty to avoid errors

if self.head == self.tail: # single node

handle case where only one node exists

self.tail = self.tail.prev

move tail pointer back to previous node

self.tail.next = None

unlink the old tail node from the list

Output

Before deletion: 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5 ← tail

Deleted node: 5

After deletion: 1 ↔ 2 ↔ 3 ↔ 4 ← tail

Complexity Analysis

Time: O(n) because we traverse from head to tail to find the last node if tail pointer is not maintained; here tail pointer is maintained so O(1) for deletion

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

vs Alternative: Without a tail pointer, deletion from end requires O(n) traversal; with tail pointer, deletion is O(1)

Edge Cases

empty list

delete_from_end returns None and list remains empty

DSA Python

if not self.tail:  # empty list

single node list

deletes the only node and sets head and tail to None

DSA Python

if self.head == self.tail:  # single node

When to Use This Pattern

When you need to remove the last element quickly from a doubly linked list, use the tail pointer to delete in O(1) time.

Common Mistakes

Mistake: Not updating the tail pointer after deletion
Fix: Always move tail to tail.prev and set tail.next to None

Mistake: Not handling empty or single node list cases
Fix: Add checks for empty list and single node list before deletion

Summary

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

Use when you want to remove the last element efficiently from a doubly linked list.

The key is to update the tail pointer and unlink the last node to maintain list integrity.

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