Next, let’s consider the implementation of SimpleLinkedList::removeLast(). This function’s job is simply to remove the last node in the list. This job will require us to traverse the entire list to find the last node. Once we find it, we need to delete it and set the next pointer of the previous node to nullptr.
Starting with current == nullptr, it is clear we would have an issue. Detecting that we went “one step too far” means we missed our opportunity to delete the last node. For this algorithm, we need to stop earlier.
Next, consider current->next == nullptr. In this case, we are at the last node. However, we have no way to update the previous node’s next pointer to nullptr because we don’t have a pointer to the previous node:
When we used iteration, we designed the removeAt and insertAt to stop one earlier than the target index so that we could update the next pointer of whatever node needed to be changed. We could do the same thing here by using current->next->next == nullptr as our base case:
There is a downside to looking ahead two nodes like this. If the list has only one node, then current->next will be nullptr, and trying to access current->next->next will cause a runtime error. We could add a check in our member function to see if the list has only one node and handle that case separately. (In addition to the special case we will need for if the list is empty.) Fortunately, there is a way to avoid this extra check.
To avoid the extra case, we need to use current->next == nullptr as our base case. But we still need a way to update the previous node’s next pointer. We can do that by having our recursive function return a pointer to the caller. This pointer will be the updated pointer that the caller should use.
ListNode* recursiveRemoveLast(ListNode* current) {
if(current->next == nullptr) {
delete current;
return nullptr; // I was deleted!
}
else {
current->next = recursiveRemoveLast(current->next);
return current; // I'm still here!
}
}
void SimpleLinkedList::removeLast() {
if(head != nullptr)
head = recursiveRemoveLast(head);
}
When a node is deleted, we will return nullptr to the caller. If a node is not deleted, we will return the original current pointer back to the caller. This way, each call can update its next pointer based on what the callee returns. In our list of {6, 10, 3}, we would produce the following series of calls:
myList::removeLast() would call recursiveRemoveLast(head) (on the 6 node)
recursiveRemoveLast({10 node}) would receive nullptr from its callee and set its next pointer to nullptr, then return its own current pointer (the 10 node) to its caller
recursiveRemoveLast({6 node}) would receive the 10 node pointer from its callee and set its next pointer to that value, then return its own current pointer (the 6 node) to its caller
In this implementation, each node is responsible for updating its own next pointer, but what it updates it to is “someone else’s problem”. The next node in the chain will either let the caller know that it was deleted (by returning nullptr) or that it is still there (by returning its own pointer).
The key bits are shown in the listing below. On either line 4 or 8, we return the correct pointer. The caller stores whatever value that is into its own next pointer on line 7. Eventually, this propagates all the way back to the original call in removeLast, which updates the head pointer. Most of those assignments will not actually change anything. The only next pointer that should actually change is the one in the call that gets a nullptr back from its callee.
ListNode* recursiveRemoveLast(ListNode* current) {
if(current->next == nullptr) {
delete current;
return nullptr; // I was deleted!
}
else {
current->next = recursiveRemoveLast(current->next);
return current; // I'm still here!
}
}
void SimpleLinkedList::removeLast() {
if(head != nullptr)
head = recursiveRemoveLast(head);
}
Note28.11.1.
This technique may feel a little mind bending at first. However, it is a common strategy in recursive algorithms where nodes need to be removed from a linked structure. In more complex structures, eliminating special cases can greatly simplify the code.
It is also very “true” to the philosophy of recursion. Each node is responsible for managing its own state and delegating the rest of the work to recursive calls. No one ever needs to inspect or change the thing that its next pointer points to.
The implementation below includes lots of debugging information about the memory addresses being returned and set. You can see that version of the code in Listing 28.14.1
Implement a recursive insertLast function. It should add a new node with the given value to the end of the list using the strategy of returning the address of the updated list.
