Delete from End of Doubly Linked List in DSA C++ - 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?

↓

Delete node, set head and tail to null

↓

Move tail pointer to previous node

↓

Set new tail's next to null

↓

Done

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

Execution Sample

DSA C++

void deleteFromEnd() {
  if (!tail) return;
  if (head == tail) {
    delete tail;
    head = tail = nullptr;
    return;
  }
  Node* temp = tail;
  tail = tail->prev;
  tail->next = nullptr;
  delete temp;
}

Deletes the last node from a doubly linked list, updating tail and 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	Delete tail node (40)	10 <-> 20 <-> 30	tail moves from 40 to 30; 30.next set to null	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ prev:∅ │←── │ prev:10│←── │ prev:20│ │ next:20│──→ │ next:30│──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head tail
3	Delete tail node (30)	10 <-> 20	tail moves from 30 to 20; 20.next set to null	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ prev:∅ │←── │ prev:10│ │ next:20│──→ │ next:∅ │ └────────┘ └────────┘ head tail
4	Delete tail node (20)	10	tail moves from 20 to 10; 10.next set to null	┌────────┐ │ data:10│ │ prev:∅ │ │ next:∅ │ └────────┘ head & tail
5	Delete tail node (10), list becomes empty	empty	head and tail set to null	∅ (empty list)
6	Try delete on empty list	empty	No change	∅ (empty list)

💡 Execution stops when list is empty (head and tail are null).

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6
head	Node(10)	Node(10)	Node(10)	Node(10)	null	null
tail	Node(40)	Node(30)	Node(20)	Node(10)	null	null
tail->next	null	null	null	null	null	null
list size	4	3	2	1	0	0

Key Moments - 3 Insights

Why do we check if head == tail before deleting?

Because if head == tail, it means there is only one node. Deleting it empties the list, so we must set head and tail to null (see execution_table step 5).

Why do we set tail->next to null after moving tail?

To break the link to the deleted node and mark the new tail's next as null, indicating the end of the list (see execution_table step 2).

What happens if we try to delete from an empty list?

The function returns immediately without changes, as tail is null (see execution_table step 6).

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the tail node's data?

A 40

B 20

C 30

D 10

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 3 in execution_table.

At which step does the list become empty?

A Step 4

B Step 6

C Step 5

D Step 3

💡 Hint

Look for when head and tail become null in variable_tracker and execution_table.

If we delete from an empty list, what changes occur?

A No changes happen

B tail moves to previous node

C head and tail become null

D A new node is created

💡 Hint

See execution_table step 6 where delete is called on empty list.

Concept Snapshot

Delete from End of Doubly Linked List:
- If list empty (tail == null), do nothing.
- If one node (head == tail), delete node, set head and tail to null.
- Else move tail to tail->prev.
- Set new tail->next to null.
- Delete old tail node.
- List size decreases by one.

Full Transcript

Deleting from the end of a doubly linked list involves checking if the list is empty or has only one node. If empty, no action is taken. If only one node, deleting it empties the list by setting head and tail to null. Otherwise, the tail pointer moves to the previous node, and the new tail's next pointer is set to null to mark the end. The old tail node is then deleted. This process is repeated until the list is empty. Trying to delete from an empty list does nothing.

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