Deleting from the Tail
What you'll learn: How to remove the last node from a singly linked list by finding and updating the second-to-last node.
The Challenge with Tail Deletion
Unlike deleting from the head (which is instant), removing the last node from a singly linked list requires extra work. Why? Because each node only points forward to the next node—there's no way to jump backward. To delete the tail, you must find the second-to-last node and update its next pointer to NULL.
Why We Need to Traverse
Think of it like a train where each car is connected only to the one behind it. To disconnect the last car, you need to walk through the entire train until you reach the second-to-last car, then unhitch the connection there.
Here's the process:
- Handle special cases: If the list is empty or has only one node, handle those separately
- Traverse the list: Start at the head and move forward until you reach the node whose
nextpointer points to the tail - Update the pointer: Set that second-to-last node's
nexttoNULL - Deallocate: Free the memory of the old tail node
- Update tail pointer (if you're maintaining one): Point it to the new last node
Time Complexity
Even though we're only removing one node, we must visit every node before it to find our position. This makes tail deletion O(n) time complexity, where n is the number of nodes in the list.
Key Takeaway: Deleting from the tail of a singly linked list requires traversing the entire list to find the second-to-last node, making it an O(n) operation unlike the O(1) head deletion.