How to fix the leak in this simple Single-Linked List?

[VoB]

Hi everyone,

I have the following simple implementation of a Single-Linked List

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <memory>

template <typename T>
struct Link
{
    T val;
    Link *next;
    Link(const T &vval = T{}, Link *p = nullptr) : val{vval}, next{p} {}
};

template <typename T>
class List
{

private:
    Link<T> *first;

public:
    class Iterator;

    Iterator begin() { return Iterator(first); }
    Iterator end() { return Iterator(nullptr); }

    List() : first{nullptr} {}

    ~List(){ delete first;}
    int size() const;
    void push_front(const T& val);
    void push_back(const T &val);
    Iterator insert(Iterator p, const T &v);

};

template <typename T>
void List<T>::push_front(const T& val){
    first = new Link<T>(val,first);
}

template <typename T>
typename List<T>::Iterator List<T>::insert(Iterator p, const T &v)
{
    Link<T> *tmp = p.current->next;
    Link<T> *new_elem = new Link<T>(v, tmp);
    p.current->next = new_elem;
    return Iterator(new_elem);
}

template <class T>
void List<T>::push_back(const T &v)
{
    Iterator p1 = begin();
    while (true)
    {
        Iterator p2 = p1;
        ++p2;
        if (!p2.current)
        {
            this->insert(p1, v);
            return;
        }
        ++p1;
    }
}

template <typename T>
class List<T>::Iterator
{
    friend class List<T>;
    Link<T> *current;

public:
    Iterator(Link<T> *p) : current{p} {}
    Iterator &operator++()
    {
        current = current->next;
        return *this;
    }
    T &operator*() { return current->val; }

    bool operator==(const Iterator &b) { return current == b.current; }
    bool operator!=(const Iterator &b) { return !(*this == b); }
};

int main()
{

    List<int> l{};
    l.push_front(10);
    l.push_front(20);
    l.push_back(19);
    l.push_back(29);
    for (auto& x:l)
    {
        std::cout << x <<'\n';
    }
    
    return 0;
}

I am already able to do a Linked-List with smart pointers, which means in this particular case that I can use std::unique_ptr. However, I wanted to try with raw ones for learning purposes.

So far, I am having a memory leak, and it's coming from line 47 in the insert function.
How can I fix it? I was thinking to just plug a destructor ~Link(){delete next;} in the Link struct, so when a Link goes out of scope in a function, then its is automatically destroyed, but I don't know if this is the right choice. (Notice that I also deleted first, my head, in ~List )



I'd like to understand how I can fix this. Even other workarounds are much appreciated.

Best

[seeplus]

The destructor isn't correct. You need to traverse the list links and delete the allocated memory for each node.

[VoB]

Thanks for your answer @seeplus.

However, if I plug ~Link(){delete next;}, then I see no memory leaks. Why can't this be the correct workaround?

Thanks

[VoB]

I updated my code in this way: notice the destructor of List at line 31: please tell me if I am doing precisely what you meant. I have seen that so far I have no memory leaks.

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <memory>

template <typename T>
struct Link
{
    T val;
    Link *next;
    Link(const T &vval = T{}, Link *p = nullptr) : val{vval}, next{p} {}
};

template <typename T>
class List
{

private:
    Link<T> *first;

public:
    class Iterator;

    Iterator begin() { return Iterator(first); }
    Iterator end() { return Iterator(nullptr); }

    List() : first{nullptr} {}

    ~List()
    {
        auto it = begin();

        while (it != this->end())
        {
            delete it.current;
            ++it;
        }
    }
    int size() const;
    void push_front(const T &val);
    void push_back(const T &val);
    Iterator insert(Iterator p, const T &v);

};

template <typename T>
void List<T>::push_front(const T &val)
{
    first = new Link<T>(val, first);
}

template <typename T>
typename List<T>::Iterator List<T>::insert(Iterator p, const T &v)
{
    Link<T> *tmp = p.current->next;
    Link<T> *new_elem = new Link<T>(v, tmp);
    p.current->next = new_elem;
    return Iterator(new_elem);
}

template <class T>
void List<T>::push_back(const T &v)
{
    Iterator p1 = begin();
    while (true)
    {
        Iterator p2 = p1;
        ++p2;
        if (!p2.current)
        {
            this->insert(p1, v);
            return;
        }
        ++p1;
    }
}

template <typename T>
class List<T>::Iterator
{
    friend class List<T>;
    Link<T> *current;

public:
    Iterator(Link<T> *p) : current{p} {}
    Iterator &operator++()
    {
        current = current->next;
        return *this;
    }
    T &operator*() { return current->val; }

    bool operator==(const Iterator &b) { return current == b.current; }
    bool operator!=(const Iterator &b) { return !(*this == b); }
};

int main()
{

    List<int> l{};
    l.push_front(10);
    l.push_front(20);
    l.push_back(19);
    l.push_back(29);
    for (auto &x : l)
    {
        std::cout << x << '\n';
    }
    l.push_back(29);
    l.push_front(2);
    l.push_back(29);
    l.push_front(2);
    for (auto &x : l)
    {
        std::cout << x << '\n';
    }


    return 0;
}

[seeplus]

 ~List()
    {
        auto it = begin();

        while (it != this->end())
        {
            delete it.current;
            ++it;
        }
    }

I don't think so. ++it does current = current->next - but you're just deleted current!
You need to get the address of the next node before you delete the memory of the current one. Without using iterators, the usual code would be something like:

while (head != nullptr) {
    const auto cur {head};

    head = head->next;
    delete cur;
}

[VoB]

Thanks @seeplus, I've understand the issue now. I have just written the following destructor, but using iterators now. I think it's doing the same thing you wrote in your last snippet. Do you agree? After this check, I can consider the topic closed :-)

~List(){
auto it = begin();
while (it!=nullptr)
{
    const auto current_node = it.current;
    ++it;
    delete current_node;
}
}

[seeplus]

for (auto it {begin(); it != end(); ) {
    const auto current_node {it.current};

    ++it;
    delete current_node;
}

assuming that end() returns nullptr which I think it does from your code above.

[VoB]

Ah yes, that for loop is really the classical way to traverse a container... don't know why I wrote that while. Btw, thanks a lot for your help @seeplus

Now things are much more clear. :-)