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

The Big Idea

What if you could remove the last item from a list instantly without searching through everything?

The Scenario

Imagine you have a long chain of paper clips linked together. You want to remove the last paper clip from the chain. Doing this by hand means you have to carefully find the second last clip and detach the last one without breaking the chain.

The Problem

Manually finding the second last paper clip every time is slow and easy to mess up. You might accidentally break the chain or lose track of the clips. This is like scanning through a list from the start every time you want to remove the last item, which wastes time and can cause errors.

The Solution

A doubly linked list keeps track of both the next and previous clips. This means you can quickly jump to the last clip and remove it by updating just a few links, without scanning the whole chain. It makes removing the last item fast and safe.

Before vs After

✗ Before

Node* current = head;
while (current->next->next != nullptr) {
    current = current->next;
}
// remove current->next

✓ After

Node* last = tail;
tail = tail->prev;
if (tail != nullptr) {
    tail->next = nullptr;
} else {
    head = nullptr;
}
delete last;

What It Enables

This lets you efficiently remove the last item from a list anytime, making your programs faster and more reliable.

Real Life Example

Think of a music playlist where you want to remove the last song quickly without going through the entire list of songs.

Key Takeaways

Manually removing the last item requires scanning the list, which is slow.

Doubly linked lists store backward links, allowing quick access to the last item.

Deleting from the end updates just a few pointers, making it fast and safe.

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