Linked linked destructor raises segmentation fault [closed]

Question

I am trying to delete a linked list using the destructor.

But this code is giving a segmentation fault:

~Node()
{
    Node *current = this ;
    Node *previous = NULL;
    while(current != NULL)
    {
        previous = current;
        current = current->next;
        delete previous;
        previous = NULL;
    }
}

What am I doing wrong here?

Answer 1

You should exclude the current node from the delete operator, as the code is already a response to such a delete. Doing it again is like running in circles.

So modify your code to this:

~Node()
{
    Node *current = this->next; // exclude current node
    Node *previous;

    while (current != NULL)
    {
        previous = current;
        current = current->next;
        previous->next = NULL; // avoid the delete below to propagate through list.
        delete previous;
    }
}

There is no need to set previous to NULL, since it will run out of scope. But it is needed to detach previous from its successors, so to avoid the the destructor will follow that chain again.

This code assumes that this is the first node of the list, which would be the natural thing to execute delete on. If for some reason you would execute delete on a node somewhere in the middle of a list, with the aim to discard the whole list, then you would need to repeat the above loop also for the nodes that precede the current node.

Answer 2

You may not delete the current node itself because otherwise the code invokes undefined behavior.

Instead you could write

~Node()
{
    delete next;
}

And if the list is defined as a pointer to the head node then you need to write

delete head;

Here is a demonstration program

#include <iostream>

class Node
{
private:
    int data;
    Node *next;

public:

    explicit Node( int data, Node *next = nullptr ) : data( data ), next( next )
    {
    }

    ~Node()
    {
        std::cout << "Deleting " << data << "...\n";
        delete next;
    }
};

void push_front( Node *&head, int data )
{
    head = new Node( data, head );
}

int main()
{
    Node *head = nullptr;
    const int N = 10;

    for (int i = 0; i < N; i++)
    {
        push_front( head, N - i );
    }

    delete head;
}

The program output is

Deleting 1...
Deleting 2...
Deleting 3...
Deleting 4...
Deleting 5...
Deleting 6...
Deleting 7...
Deleting 8...
Deleting 9...
Deleting 10...