Delete from End of Doubly Linked List in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a doubly linked list?

A doubly linked list is a chain of nodes where each node has three parts: data, a pointer to the next node, and a pointer to the previous node. This allows traversal in both directions.

beginner

What happens when you delete the last node from a doubly linked list?

The last node is removed, the second last node's next pointer is set to null, and if the list becomes empty, the head pointer is set to null.

intermediate

Why do we need to update the previous node's next pointer when deleting from the end of a doubly linked list?

Because the second last node's next pointer must be set to null to disconnect the last node and prevent a dangling reference from the second last node to the deleted node. The second last node's previous pointer remains unchanged.

beginner

Show the steps to delete the last node in a doubly linked list.

1. Check if the list is empty; if yes, do nothing.
2. If only one node, delete it and set head to null.
3. Otherwise, traverse to the last node.
4. Set the second last node's next pointer to null.
5. Delete the last node.

intermediate

What is the time complexity of deleting the last node in a doubly linked list if no tail pointer is used?

O(n), because you need to traverse from the head to the last node to delete it.

What pointer must be updated when deleting the last node in a doubly linked list?

A The head pointer

B The previous node's next pointer

C The last node's next pointer

D The previous node's previous pointer

The previous node's next pointer must be set to null to remove the last node.

If a doubly linked list has only one node, what happens after deleting that node?

A Head pointer is set to null

B Tail pointer points to the node

C Next pointer points to itself

D List becomes circular

After deleting the only node, the list becomes empty, so head is set to null.

What is the best way to optimize deletion from the end of a doubly linked list?

A Maintain a tail pointer

B Use a singly linked list

C Traverse from head every time

D Use an array instead

Maintaining a tail pointer allows direct access to the last node, making deletion O(1).

Which of these is NOT true about deleting the last node in a doubly linked list?

A You must update the previous node's next pointer

B If the list is empty, no deletion occurs

C You must update the last node's previous pointer to null

D If only one node exists, head becomes null after deletion

The last node is deleted, so its pointers do not need updating; only the previous node's next pointer is updated.

What is the time complexity of deleting the last node if a tail pointer is maintained?

A O(n^2)

B O(n)

C O(log n)

D O(1)

With a tail pointer, deletion from the end is done in constant time.

Explain how to delete the last node from a doubly linked list step-by-step.

Think about what pointers need changing and what happens when the list has one or no nodes.

Describe the difference in deleting the last node in a doubly linked list with and without a tail pointer.

Focus on how the tail pointer helps avoid traversal.

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