Delete from End of Doubly Linked List in DSA C++

Mental Model

To remove the last item, 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 where you want to remove the last carriage. You detach it from the second last carriage, and 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: Check if tail is null: no

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

Why: Handle empty list case

Step 2: val = tail->data (5)

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

Why: Store value before deletion

Step 3: toDelete = tail (node 5)

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

Why: Save reference to node for deletion

Step 4: head != tail, tail = tail->prev (node 4)

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

Why: Update tail to second-last node

Step 5: tail->next = nullptr

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

Why: Unlink the old tail node

Step 6: delete toDelete

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

Why: Free memory of removed node

Result:

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

Annotated Code

DSA C++

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node* prev;
    Node(int val) : data(val), next(nullptr), prev(nullptr) {}
};

class DoublyLinkedList {
public:
    Node* head;
    Node* tail;
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}

    void append(int val) {
        Node* newNode = new Node(val);
        if (!head) {
            head = tail = newNode;
            return;
        }
        tail->next = newNode;
        newNode->prev = tail;
        tail = newNode;
    }

    int deleteFromEnd() {
        if (!tail) return -1; // empty list
        int val = tail->data;
        Node* toDelete = tail;
        if (head == tail) { // single node
            head = tail = nullptr;
        } else {
            tail = tail->prev; // move tail back
            tail->next = nullptr; // unlink last node
        }
        delete toDelete;
        return val;
    }

    void printList() {
        Node* curr = head;
        while (curr) {
            cout << curr->data;
            if (curr->next) cout << " ↔ ";
            curr = curr->next;
        }
        cout << "\n";
    }
};

int main() {
    DoublyLinkedList dll;
    dll.append(1);
    dll.append(2);
    dll.append(3);
    dll.append(4);
    dll.append(5);

    cout << "Original list: ";
    dll.printList();

    int deletedValue = dll.deleteFromEnd();
    cout << "Deleted node value: " << deletedValue << "\n";

    cout << "List after deletion: ";
    dll.printList();

    return 0;
}

if (!tail) return -1; // empty list

check if list is empty to avoid errors

int val = tail->data;

store value of last node to return after deletion

if (head == tail) { head = tail = nullptr; }

handle single node list by clearing head and tail

tail = tail->prev; // move tail back

move tail pointer to previous node

tail->next = nullptr; // unlink last node

unlink last node from list

delete toDelete;

free memory of removed node

Output

Original list: 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5

Deleted node value: 5

List after deletion: 1 ↔ 2 ↔ 3 ↔ 4

Complexity Analysis

Time: O(1) because we directly access the tail node 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 O(n) traversal, doubly linked list allows O(1) deletion from end

Edge Cases

empty list

returns -1 indicating no node to delete

DSA C++

if (!tail) return -1; // empty list

single node list

head and tail become nullptr after deletion

DSA C++

if (head == tail) { head = tail = nullptr; }

When to Use This Pattern

When you need to remove the last element quickly from a list, and you have two-way links, use the doubly linked list delete from end pattern for O(1) removal.

Common Mistakes

Mistake: Not updating tail pointer after deletion, leaving tail pointing to deleted node
Fix: Always move tail to tail->prev and set tail->next to nullptr

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

Summary

Deletes the last node from a doubly linked list efficiently.

Use when you want to remove the end element quickly without traversing the whole list.

The key is to update the tail pointer and unlink the last node safely.

Practice

1. What happens to the tail pointer when you delete the last node from a doubly linked list?

easy

A. It moves to the previous node of the deleted node

B. It becomes null immediately

C. It points to the head node

D. It remains unchanged

Solution

1. Step 1: Understand the tail pointer role

   The tail pointer always points to the last node in the list.

2. Step 2: Effect of deleting the last node

   When the last node is deleted, the tail must move to the previous node to remain the last node.

3. Final Answer:

   It moves to the previous node of the deleted node -> Option A

4. Quick Check:

   Tail updates to previous node after deletion [OK]

Hint: Tail always points to last node, update to previous on delete [OK]

Common Mistakes:

• Setting tail to null without checking if list is empty
• Not updating tail pointer after deletion
• Pointing tail to head incorrectly

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

easy

A. tail->prev = tail; delete tail; tail = nullptr;

B. delete tail; tail = tail->prev; tail->next = nullptr;

C. tail = tail->prev; delete tail->next; tail->next = nullptr;

D. tail->next = nullptr; delete tail; tail = tail->prev;

Solution

1. Step 1: Identify correct order of operations

   First, move tail pointer to previous node, then delete the old last node, and finally set new tail's next to nullptr.

2. Step 2: Match with options

   tail = tail->prev; delete tail->next; tail->next = nullptr; correctly moves tail, deletes old node, and updates next pointer.

3. Final Answer:

   tail = tail->prev; delete tail->next; tail->next = nullptr; -> Option C

4. Quick Check:

   Move tail first, then delete old node [OK]

Hint: Move tail before deleting old node to avoid dangling pointer [OK]

Common Mistakes:

• Deleting tail before moving pointer causes invalid access
• Not setting tail->next to nullptr after deletion
• Incorrect pointer assignments causing memory leaks

3. What will be the output of the following code snippet after deleting the last node?

struct Node {
  int data;
  Node* prev;
  Node* next;
};

Node* head = new Node{1, nullptr, nullptr};
Node* second = new Node{2, head, nullptr};
head->next = second;
Node* tail = second;

// Delete last node
Node* temp = tail;
tail = tail->prev;
tail->next = nullptr;
delete temp;

// Print list
Node* curr = head;
while(curr) {
  std::cout << curr->data << " ";
  curr = curr->next;
}

medium

A. 1 2

B. No output (empty list)

C. 2

D. 1

Solution

1. Step 1: Understand list before deletion

   List has two nodes: 1 (head) -> 2 (tail).

2. Step 2: Delete last node and update pointers

   Last node (2) is deleted, tail moves to node 1, and tail->next is set to nullptr.

3. Step 3: Print remaining list

   Only node 1 remains, so output is "1".

4. Final Answer:

   1 -> Option D

5. Quick Check:

   Last node deleted, only head remains [OK]

Hint: After deleting tail, print from head to see remaining nodes [OK]

Common Mistakes:

• Printing deleted node due to not updating tail->next
• Assuming list is empty after deletion
• Confusing head and tail pointers

4. Identify the error in the following code that deletes the last node of a doubly linked list:

void deleteEnd(Node*& tail) {
  delete tail;
  tail = tail->prev;
  tail->next = nullptr;
}

medium

A. Not updating head pointer causes memory leak

B. Accessing tail->prev after deleting tail causes undefined behavior

C. tail->next should be set to tail->prev

D. No error, code is correct

Solution

1. Step 1: Analyze order of operations

   The code deletes tail first, then tries to access tail->prev which is invalid after deletion.

2. Step 2: Correct approach

   First move tail pointer to previous node, then delete the old tail node, and update pointers.

3. Final Answer:

   Accessing tail->prev after deleting tail causes undefined behavior -> Option B

4. Quick Check:

   Delete after pointer update to avoid invalid access [OK]

Hint: Move pointer before delete to avoid invalid memory access [OK]

Common Mistakes:

• Deleting node before updating pointers
• Not checking if tail is nullptr before access
• Confusing order of pointer updates and deletion

5. Given a doubly linked list with nodes containing values [10, 20, 30, 40], write the steps to delete the last node and update the list correctly. What will be the final list after deletion?

hard

A. [10, 20, 30]

B. [10, 20, 30, 40]

C. [20, 30, 40]

D. [10, 20, 40]

Solution

1. Step 1: Identify the last node and tail pointer

   The last node has value 40, tail points to it.

2. Step 2: Move tail pointer to previous node and delete last node

   Tail moves to node with value 30, delete node 40, set tail->next to nullptr.

3. Step 3: Final list after deletion

   List nodes are now 10 -> 20 -> 30 with tail at 30.

4. Final Answer:

   [10, 20, 30] -> Option A

5. Quick Check:

   Last node removed, tail updated, list shortened [OK]

Hint: Delete last node, move tail back, set tail->next null [OK]

Common Mistakes:

• Not updating tail->next to nullptr
• Deleting wrong node or skipping pointer updates
• Assuming list shrinks from head instead of tail