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

An alternative to Abel's answer with the Node-destroying Nodes:

LinkedList::~LinkedList()
{
    while (head)
    {
        Node * temp = head;
        head = head->next;
        delete temp;
    }
}

The LinkedList loops removes, and deletes the first Node until there are no Nodes left.

Why do I prefer this approach? Two reasons:

Ownership. Who is responsible for managing the nodes? With the loop, managing the Nodes is entirely in the hands of LinkedList. If Nodes can destroy one another, management is split between LinkedList and Node, and both owners need to remain in agreement about the state of the managed resource. Maintaining this agreement is tricky and tricky means more code you can get wrong. For example, if LinkedList isn't careful when removing a single Node from the list, that Node will recursively destroy the rest of the list. Ooops.

The second reason is recursion. If the list gets too long, the program will exhaust its automatic storage (Usually causing a Stack Overflow) and become unstable. You've limited the size of the list you can handle unnecessarily and the only way you'll know you've exceeded the limit is when the program fails.

The access violation the Asker has been experiencing I have been unable to reproduce. I may have accidentally fixed it.

Answer 2

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