Deleting from the Tail of a Doubly Linked List
You'll learn how to efficiently remove the last node from a doubly linked list by leveraging backward links.
The Core Idea
In a singly linked list, deleting the tail requires traversing from the head to find the second-to-last node—it's slow. But in a doubly linked list, each node has a prev pointer pointing backward. This means if you maintain a tail pointer, you can instantly access the last node and the one before it, making tail deletion much faster.
The Process
Think of it like a chain where each link knows both its neighbors. To remove the last link:
- Start at the tail – You already have direct access via your tail pointer
- Find the new tail – Use
tail->prevto instantly jump to the second-to-last node - Disconnect the old tail – Set the new tail's
nextpointer toNULL - Update the tail pointer – Move it backward to point at the new last node
- Free the memory – Deallocate the removed node
Special Cases
Empty list: If tail is NULL, there's nothing to delete.
Single node: If tail->prev is NULL, you're deleting the only node. Both head and tail should become NULL.
The Backward Advantage
The beauty here is the prev pointer. Without it, you'd have to walk the entire list from the head. With it, you jump straight to the node that needs updating—constant time access instead of linear traversal.
Key Takeaway: Deleting from the tail of a doubly linked list uses the prev pointer to quickly find and update the new tail, setting its next to NULL and moving the tail pointer backward—making this operation efficient compared to singly linked lists.