CODEWITHSUNDEEP
c++pointerslinked-list
user3587244
user3587244

Reputation: 173

Removing last element in LinkedList (C++)

I am writing a function to delete the last node in a linked list. This is what I have, and other code I've found online searching for a solution is very similar (I have found several), but when I execute it it creates some sort of infinite loop when deleting the last element of a linked list (it deletes other elements just fine though).

Here is the code I imagine is causing a problem:

void delete_final(Node* head){
    if(head == NULL) {
        return; }
    if(head->next == NULL) {
        delete head;
        head = NULL;
        return;
    }  
//other code 
}

I imagine it's an issue with the memory (particularly after the delete head; statement), but I'm really stuck and would appreciate any help or an explanation for why this doesn't work (I possibly don't have a very good understanding of pointers and memory in C++, I'm just starting with it)

Here is my Node code for reference:

struct Node {
  int key;
  Node* next;
};

Thanks for any help!

Upvotes: 0

Views: 1351

Answers (1)

Cheers and hth. - Alf
Cheers and hth. - Alf

Reputation: 145279

Original code:

void delete_final(Node* head){
    if(head == NULL) {
        return; }
    if(head->next == NULL) {
        delete head;
        head = NULL;
        return;
    }  
//other code 
}

The "other code" is not specified, but if the list has exactly one node then the above code will

  • delete that first node, and

  • update the local pointer head, which doesn't update the actual argument since it was passed by value.

As a result the calling code will be left with a dangling pointer in this case, a pointer pointing to a destroyed object, or to where such an object once was. Any use of such a pointer is Undefined Behavior. It might appear to work, or crash, or just silently cause dirty words tattoo to appear on your forehead – anything…

One fix is to pass the first-pointer by reference:

void delete_final(Node*& head){
    if(head == nullptr) {
        return; }
    if(head->next == nullptr) {
        delete head;
        head = nullptr;
        return;
    }  
//other code 
}

A nice helper function for dealing with linked lists, is unlink:

auto unlink( Node*& p )
    -> Node*
{
    Node* const result = p;
    p = p->next;
    return result;
}

The implementation is perhaps a bit subtle, but all you need to remember to use it is that it updates the pointer you pass as argument, which should be either a first-node pointer or a next pointer in the list, and returns a pointer to the unlinked node.

So e.g. you can do

delete unlink( p_first );

Upvotes: 3

Related Questions