Removing the last node, and updating the tail to the last node

Question

I want to remove the last node in my linked list, but it seems like I'm doing something wrong, since no element gets deleted.

void deleteTail(){
    node *temp = head;
    int iterator = 1;
    if (head == NULL)
    {
        cout<<"Nothing to be deleted."<<endl;
    }
    else if (head == tail)
    {
        temp = head;
        delete(temp);
        head = NULL;
        tail = NULL;
    }
    else
    {
        while(temp->next != NULL){
            temp = temp -> next;
        }
        tail = temp;
        temp = temp->next;
        delete(temp);
    }
}

If the linked list was 1->2->3->4->5->NULL I want it to turn into 1->2->3->4->NULL. What am I doing wrong in my code? Thanks in advance!

@user4581301 I'm sorry for the confusion caused, I'm actually trying to delete the last node, updated the post! — bqubique, Apr 11 '19 at 21:01
Thanks. This makes much more sense. You'll need to iterate through the list until you find the link who's `next` is `tail`. Set its `next` to `NULL` to cut off `tail`. Delete `tail` and set `tail` to point at the link you found. — user4581301, Apr 11 '19 at 21:07
Close, but not quite. After `while(temp->next != NULL)`, you know that `temp->next == NULL`, so you've lost the previous node and have the tail node. And because `temp->next == NULL`, `temp = temp->next;` sets `temp` to `NULL`, so `delete(temp);` is effectively `delete(NULL);`. Nothing is done. You want `while(temp->next != tail)`. — user4581301, Apr 11 '19 at 21:12

valek · Accepted Answer · 2019-04-11T21:27:07.937

2

This should do the job.

while (temp->next != NULL && temp->next->next != NULL) {
    temp = temp->next;
}

tail = temp;
delete temp->next;
temp->next = NULL;

The problem was at the end of the loop, temp is pointing at the last element. After that, you are setting temp to temp->next, or in other words to NULL. After that you are calling delete over NULL which does nothing.

Edit: Of course, this goes into the last else block.

edited Apr 11 '19 at 21:27

answered Apr 11 '19 at 21:08

valek

1,365
16
27

Doesn't condition of the while loop, while(temp->next !=NULL), bring my temp node to the node before the last one? – bqubique Apr 11 '19 at 21:11
2

@BlinQipa No, `temp->next != NULL` brings it to the last element, not the one before. `temp->next == NULL` is true only for the last element. The condition `temp->next->next != NULL` stops the loop at the node before the last one because if `temp` points at the element before the last one, then `temp->next` points at the last one and `temp->next->next` is `NULL`. – valek Apr 11 '19 at 21:15

J.R. · Answer 2 · 2019-04-11T21:31:02.663

EDIT: This removes the second to last node since this was the original question.

You'll need to keep track of the previous nodes. When you remove the node prior to the last one (second to last node) then the tail remains the same but you have to point the node prior to the second-to-last node to the tail:

while (temp->next != NULL) {
    if ((temp->next->next != NULL) &&        
        (temp->next->next->next == NULL)) {  // the second node after temp is tail
        delete temp->next;                   // delete second-to-last node
        temp->next = tail;       // two nodes back set to tail
        break;
    }
    temp = temp->next;
}

user4581301 · Answer 3 · 2019-04-11T21:26:34.417

while(temp->next != NULL){
    temp = temp -> next;
}
tail = temp;
temp = temp->next;
delete(temp);

is really close, but while(temp->next != NULL) is only false at the end of the linked list. This means the code has iterated to the last node, assigned tail to itself and deleted the null pointer terminating the linked list.

Instead use

while(temp->next != tail){
    temp = temp -> next;
}
tail = temp;
temp = temp->next;
delete(temp);
tail->next = NULL;

This will stop on the node that points to tail, the second last item in the list, assign the second last as the new tail, delete the old tail, and terminate the new tail with a NULL

There is an excellent general case using a pointer to a pointer here that simplifies the code greatly.

Removing the last node, and updating the tail to the last node

3 Answers3