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

↓

Is tail null?

Yes→List empty, nothing to delete

No↓

Move tail to tail.prev

↓

Set new tail.next to null

↓

Delete old tail node

↓

Done

Start from the tail node, check if list is empty, move tail pointer back, update links, and delete the last node.

Execution Sample

DSA C

void deleteFromEnd(Node** head, Node** tail) {
    if (*tail == NULL) return;
    Node* toDelete = *tail;
    *tail = (*tail)->prev;
    if (*tail) (*tail)->next = NULL;
    else *head = NULL;
    free(toDelete);
}

Deletes the last node from a doubly linked list by updating tail and head pointers and freeing memory.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with list 10 <-> 20 <-> 30 (tail=30)	10 <-> 20 <-> 30	head → 10, tail → 30	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ prev:∅ │←── │ prev:10│←── │ prev:20│ │ next:20│──→ │ next:30│──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head tail
2	Check if tail is NULL (No)	10 <-> 20 <-> 30	No pointer change	Same as step 1
3	Set toDelete = tail (30)	10 <-> 20 <-> 30	toDelete → 30	Same as step 1
4	Move tail to tail.prev (20)	10 <-> 20 <-> 30	tail: 30 → 20	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ prev:∅ │←── │ prev:10│←── │ prev:20│ │ next:20│──→ │ next:30│──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head tail (moved) toDelete
5	Set tail.next = NULL	10 <-> 20	20.next: 30 → NULL	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ prev:∅ │←── │ prev:10│←── │ prev:20│ │ next:20│──→ │ next:∅ │ │ next:∅ │ └────────┘ └────────┘ └────────┘ head tail toDelete
6	Free toDelete (30)	10 <-> 20	toDelete removed	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ prev:∅ │←── │ prev:10│ │ next:20│──→ │ next:∅ │ └────────┘ └────────┘ head tail
7	Done	10 <-> 20	head → 10, tail → 20	Final list after deletion

💡 Deletion complete; tail updated and last node removed

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	After Step 6	Final
head	10	10	10	10	10	10
tail	30	30	20	20	20	20
toDelete	NULL	30	30	30	NULL	NULL

Key Moments - 3 Insights

Why do we move tail to tail.prev before deleting the node?

Because we need to update the tail pointer to the new last node before removing the old tail. See step 4 in execution_table where tail moves from 30 to 20.

What happens if the list has only one node?

After deletion, both head and tail become NULL. This is handled in the code by setting head to NULL if tail becomes NULL (not shown in this example but important).

Why do we set tail.next to NULL after moving tail?

To disconnect the new tail from the deleted node, ensuring the list ends properly. See step 5 where 20.next changes from 30 to NULL.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the new value of tail?

A Node with data 30

B Node with data 20

C NULL

D Node with data 10

💡 Hint

Check the 'Pointer Changes' column at step 4 in execution_table

At which step does the tail's next pointer become NULL?

A Step 6

B Step 3

C Step 5

D Step 2

💡 Hint

Look at the 'Operation' and 'Pointer Changes' columns in execution_table

If the list had only one node, what would happen to head after deletion?

A It becomes NULL

B It points to tail

C It remains pointing to the deleted node

D It points to itself

💡 Hint

Refer to key_moments about single node list behavior

Concept Snapshot

Delete from End of Doubly Linked List:
- Start at tail node
- If tail is NULL, list is empty
- Move tail pointer to tail.prev
- Set new tail.next to NULL
- Free old tail node
- Update head to NULL if list becomes empty

Full Transcript

To delete the last node from a doubly linked list, we start at the tail node. If the tail is NULL, the list is empty and nothing is done. Otherwise, we save the tail node to delete, move the tail pointer back to the previous node, set the new tail's next pointer to NULL to disconnect the old tail, then free the old tail node. If the list had only one node, after deletion both head and tail become NULL. This process ensures the list remains properly linked and updated after deletion.