free(): double free detected in tcache 2, in linked List deletion of a node in c++ and how destructor is working in this code

Question

class Node{
    public:
        int data;
        Node* next;
        
        Node(int d){
            data = d;
            next = NULL;
        }
        
        ~Node(){
            delete next;
        }
};

class List{
    public:
        Node* head;
        Node* tail;
        
        List(){
            head = NULL;
            tail = NULL;
        }
        
        ~List(){
            delete head;
        }
        
        void push_back(int data){
            Node* n = new Node(data);
            if(head == NULL){
                head = tail = n;
            }else{
                tail->next = n;
                tail = n;
            }
        }
        void print(){
            Node* temp = head;
            while(temp != NULL){
                cout<<temp->data<<" ";
                temp = temp->next;
            }
        }
        void deleteNode(int d){
            Node* curr = head;
            Node* prev = NULL;
            while(curr != NULL){
                if(curr->data == d){
                    if(prev == NULL){
                        head = head->next;
                        delete curr;
                        break;
                    }else{
                        prev->next = curr->next;
                        curr->next = NULL;
                        delete curr;
                        break;
                    }
                }
                prev = curr;
                curr = curr->next;
            }
        }
};

int main(){
    List l;
    l.push_back(1);
    l.push_back(2);
    l.push_back(3);
    l.push_back(4);
    l.push_back(5);
    l.deleteNode(1);
    l.print();
}

If I delete 1 from 1->2->3->4->5

Expected Output: 2->3->4->5

Output: free(): double free detected in tcache 2;

Reason: Destructor in Node Class. If I remove it is working fine.

Doubt : If I remove destructor in Node class in Node class then how can I free up memory. And can anyone also explain how destructors are working in both Node and List class.

Can someone please help me with this, or can provide alternative solution.

Thank You!!!

Answer 1

~Node(){ delete next; } makes it hard to delete a single node from that list. It'll delete all nodes after it too.

I suggest that the individual Nodes do not delete following Nodes:

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

    Node(int d) : // colon starts the member initializer list
        data(d), next(nullptr)
    {
        // the body of the constructor can now be empty
    }

    // No user-defined destructor needed here
};

Instead, delete all Nodes in the destructor of List:

    ~List() {
        for(Node* next; head; head = next) {
            next = head->next;
            delete head; 
        }
    }

---

Unrelated to the problem at hand. These are just suggestions:

You could make the constructor of Node a little more versatile so it's possible to provide the next Node already at construction:

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

    // `nullptr` below is a default argument that will be used if the
    // user of this class does not provide a second argument
    Node(int d, Node* n = nullptr) :
        data(d), next(n)
    {}
};

This could be used in a List member function called push_front:

    void push_front(int data) {
        head = new Node(data, head);
        if(!tail) tail = head;
    }

Unrelated to that, you could make push_back a little clearer without even changing the current Node at all:

    void push_back(int data) {
        Node* n = new Node(data);

        if(tail)  tail->next = n;
        else      head = n;

        tail = n;
    }