How to prevent memory leak in generalized linked list?

user_13147068 0
Viewed 146

I've implemented my own linked list data structure. Data is stored inside Node struct. Code is as follows

// NODE

template <typename T>
struct Node
{
    T data;
    Node<T> *next;
    Node(T);
};

template <typename T>
Node<T>::Node(T d) : data(d), next(NULL) {}

// LIST

#include "node.cpp"

template <typename T>
class List
{
    Node<T> *head;
    int size;

public:
    List();                       // Default constructor
    List(const List &);           // Copy constructor
    void push_back(const T &);    // Insert element to the end of the list
    int get_size() const;         // Get the current size of the list
    T &operator[](int) const;     // Overload [] operator
    void operator=(const List &); // Overload = operator
    ~List();                      // Destructor
};

template <typename T>
List<T>::List() : head(NULL), size(0) {}

template <typename T>
List<T>::List(const List &list) : head(NULL), size(0)
{
    for (int i = 0; i < list.size; i++)
        push_back(list[i]);
}

template <typename T>
void List<T>::push_back(const T &data)
{
    // Create new Node with data
    Node<T> *nn = new Node<T>(data);

    // Find insert position
    if (head == NULL)
    {
        head = nn;
        size++;
        return;
    }

    Node<T> *traverse = head;
    while (traverse->next)
        traverse = traverse->next;

    // Traverse points to end of the list
    traverse->next = nn;
    size++;
}

template <typename T>
int List<T>::get_size() const
{
    return size;
}

template <typename T>
T &List<T>::operator[](int index) const
{
    int count = 0;
    Node<T> *traverse = head;
    while (traverse && count < index)
    {
        traverse = traverse->next;
        count++;
    }
    return traverse->data;
}

template <typename T>
void List<T>::operator=(const List<T> &list)
{
    Node<T> *traverse = head;

    while (head)
    {
        traverse = head;
        head = head->next;
        delete traverse;
    }

    size = 0;
    for (int i = 0; i < list.getSize(); i++)
        push_back(list[i]);
}

template <typename T>
List<T>::~List()
{
    Node<T> *traverse = head;

    while (head)
    {
        traverse = head;
        head = head->next;
        delete traverse;
    }
}

Problem is with memory leak. Consider the following main file

#include "list.cpp"

using namespace std;

List<int *> l;

void func()
{
    int *i = new int[2];
    i[0] = 1;
    i[1] = 2;
    l.push_back(i);
}

int main()
{
    func();
    return 0;
}

This program has memory leak according to Valgrind. It is because that Node does not have a destructor so it can not delete data inside it. However, I can not add a destructor to Node because, suppose that I am using List<int> so it is an error to delete something that was not dynamically allocated. In short, whenever I use a dynamically allocated data type for List, I get memory leak. How can I overcome this situation? Thanks.

memory-leaks pointers memory linked-list c++
2 Answers

The leak in your example has nothing to with the list. You leak the same with:

void func()
{
    int *i = new int[2];
    i[0] = 1;
    i[1] = 2;
}

You have to delete what you created via new and delete[] what you created via new[]. To fix the leak:

void func()
{
    int *i = new int[2];
    i[0] = 1;
    i[1] = 2;
    l.push_back(i);
    delete [] i;
}

However, note that then after the delete[] you have a dangling pointer in the list.

It is not the Lists buisness to delete objects when you push raw pointers to it. The list cannot know if those are owning pointers or not. For example:

void func()
{
    int i = 0;
    l.push_back(&i);
}

No need to delete anything here. (Though, same here: once the function returns you have a dangling pointer in the list)

Neither of the abvove is really "ok". Don't use raw owning pointers! Use smart pointers instead. And if you want a list of integers then use a List<int> (or rather a std::list<int>).

user_41177280

Use std::unique_ptr as the data type for the nodes, eg:

List<std::unique_ptr<int[]>> l;

When each node is destroyed, its destructor will destroy its unique_ptr data, which will in turn call delete[] on the int* pointer it is holding.

user_658630
Related