How to fix memory leak with linked list?

Question

Hi I have the following code, and keep getting memory leaks, can someone help me fix this please, I've been at this for hours but cant seem to find why there is a memory leak, I am new with nodes, I think the problem is with the destructor, but can't seem to pin point exactly what, please help!

#include <iostream>

using namespace std;

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

class LinkedList {
 public:
  LinkedList() {  // constructor
    head = NULL;
  }
  ~LinkedList();  // destructor
  void insert(int val);
  void display();

 private:
  Node* head;
};


LinkedList::~LinkedList() { delete head; }
// function to add node to a list
void LinkedList::insert(int val) {
  Node* newnode = new Node();
  newnode->data = val;
  newnode->next = NULL;
  if (head == NULL) {
    head = newnode;
  } else {
    Node* temp = head;  // head is not NULL
    while (temp->next != NULL) {
      temp = temp->next;  // go to end of list
    }
    temp->next = newnode;  // linking to newnode
  }
}

void LinkedList::display() {
  if (head == NULL) {
    cout << "List is empty!" << endl;
  } else {
    Node* temp = head;
    while (temp != NULL) {
      cout << temp->data << " ";
      temp = temp->next;
    }
    cout << endl;
  }
}

int main() {
  LinkedList* list = new LinkedList();
  list->insert(999);
  list->insert(200);
  list->insert(300);
  list->insert(700);
  list->insert(500);
  cout << "Linked List data" << endl;
  list->display();
  delete list;
  return 0;
}

Answer 1

I don't think you want destructing a node to delete the entire list. You could but I think each node should be independent of the others - the linked list class is where list level things should happen.

Also, you don't want the destructor to contain the code to clear the list because you may want to clear the list at some arbitrary point - so the linked list should have a clear function that is called from the linked list destructor and can be called from other places too.

So the destructor would call this function to clear the list:

void LinkedList::clear() {
    Node* next;
    Node* temp = head;
    while (temp != NULL) {
        next = temp->next;
        delete temp;
        temp = next;
    }
    head = NULL;
}

The whole code would be:

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node() : data(0), next(NULL) {
        cout << "Constructed default node\n";
    }
    Node(int data) : data(data), next(NULL) {
        cout << "Constructed node: " << data << "\n";
    }
    ~Node() {
        cout << "Destructed node: " << data << "\n";
    }
};

class LinkedList{
public:
    LinkedList() { // constructor
        head = NULL;
    }
    ~LinkedList() {
        clear();
    }
    void insert(int val);
    void display();
    void clear();
private:
    Node* head;
};

// function to add node to a list
void LinkedList::insert(int val) {
    Node* newnode = new Node(val);
    if (head == NULL) {
        head = newnode;
    }
    else {
        Node* temp = head; // head is not NULL
        while (temp->next != NULL) { 
            temp = temp->next; // go to end of list
        }
        temp->next = newnode; // linking to newnode
    }
}

// function to delete the entire list
void LinkedList::clear() {
    Node* next;
    Node* temp = head;
    while (temp != NULL) {
        next = temp->next;
        delete temp;
        temp = next;
    }
    head = NULL;
}

// function to display the entire list
void LinkedList::display() {
    if (head == NULL) {
        cout << "List is empty!" << endl;
    }
    else {
        Node* temp = head;
        while (temp != NULL) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }
}

int main() {
    LinkedList list;
    cout << "Creating List\n";
    list.insert(999);
    list.insert(200);
    list.insert(300);
    list.insert(700); 
    list.insert(500);
    cout << "Linked List data:\n";
    list.display();
    cout << "Clearing list\n";
    list.clear();
    cout << "Creating List\n";
    list.insert(400);
    list.insert(600);
    cout << "Linked List data:\n";
    list.display();
    cout << "NOT clearing list (should happen automatically\n";
    return 0;
}

You can try it here: https://onlinegdb.com/HJlOT1ngqP

The output:

Creating List
Constructed node: 999
Constructed node: 200
Constructed node: 300
Constructed node: 700
Constructed node: 500
Linked List data:
999 200 300 700 500 
Clearing list
Destructed node: 999
Destructed node: 200
Destructed node: 300
Destructed node: 700
Destructed node: 500
Creating List
Constructed node: 400
Constructed node: 600
Linked List data:
400 600 
NOT clearing list (should happen automatically
Destructed node: 400
Destructed node: 600