Destructing a linked list

Question

I was trying to implement a linked list for solving an algorithm problem.
It basically worked, however, it turned out that I was using too much memory.
I would appreciate if someone point out defects of following destructor design.

template<typename T>
struct Node {
    Node(): item(0),next(0) {}
    Node(T x): item(x),next(0) {}
    T item;
    Node* next;
};

template <typename T>
struct List {
    List() : head(0),tail(0) {}
    Node<T>* head;
    Node<T>* tail;
    void insert(T x) {
        Node<T>* newNode = new Node<T>(x);
        if(head == NULL) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            tail = tail->next;
        }
    }

    void clearRecur(Node<T>* h) {
        if(h) {
            clearRecur(h->next);
            delete h;
        }
    }

    void clear() {
        if(head) {
            clearRecur(head);
        }
    }
};

Looks like you are leaking memory, but it's hard to tell from only that snippet of code given. — user0042, Jul 29 '17 at 08:53
For starters, you have dangling reference here. You free the list in `clearRecur`, but never change `tail` nor the element before `h` (or the head, if it is the first). The same applies for `clear`, where when you finish - `head` and `tail` are still set, but already released. — amit, Jul 29 '17 at 08:59
@PeterHwang You could. But since `Node` doesn't take ownership on anything (not autimatically allocated), that's not a big issue to have non default destructor for it. — amit, Jul 29 '17 at 09:17
As long as clear is called I don't see a memory leak. It is possible that you are using memory because of the recursive clear calls needing to allocate memory and this will also limit how many elements can be in the list to the max stack depth. You could try to replace this with a simple iterative approach and see if that helps. — Mike, Jul 29 '17 at 14:10
As for the destructor question, list should have a destructor that calls clear to do the cleanup. Since this class is allocating the memory it should take care of freeing it. — Mike, Jul 29 '17 at 14:13
And it's better to incapsulate list and note state. Normally you shouldn't allow anybody to see and change internal data as it could lead to memory leaks, corruption and inconsistency. — Mr D, Jul 29 '17 at 19:42

Scheff's Cat · Accepted Answer · 2017-07-29T14:13:20.497

A list can be cleared recursively or iteratively.

Alternatively to your (IMHO correct) version, I use a slight different approach – make the Node itself "responsible" to delete its tail. This leads to recursive clearing as well (but with less code).

Recursive clearing:

template<typename T>
struct Node {
    Node(): item(), next(nullptr) {}
    Node(T x): item(x), next(nullptr) {}

    ~Node() { delete next; } // <== recursive clearing

    T item;
    Node* next;

    // Using the default copy ctor would corrupt the memory management.
    // Deleting it lets the compiler check for accidental usage.
    Node(const Node&) = delete;
    // Deleting assignment operator as well.
    Node& operator=(const Node&) = delete;
};

template <typename T>
struct List {
    List() : head(nullptr), tail(nullptr) {}
    ~List() { clear(); }
    Node<T>* head, tail;
    void insert(T x) {
        Node<T>* newNode = new Node<T>(x);
        if (head == nullptr) head = tail = newNode;
        else {
            tail->next = newNode;
            tail = tail->next;
        }
    }

    void clear() {
        delete head;
        head = tail = nullptr;
    }

    // Using the default copy ctor would corrupt the memory management.
    // Deleting it lets the compiler check for accidental usage.
    List(const List&) = delete;
    // Delete assignment operator as well.
    List& operator=(const List&) = delete;
};

This is the way, I did it in our current project. At the first glance, it seemed enjoying simple and worked fine. I changed my mind when our beta-testers came into play. In real world projects, the lists were such long that the recursive clearing ran out of stack memory. (Yepp – a stack overflow.) I should've known better!

Thus, I made the clearing iteratively – whereby the "responsibility" is moved back from Node to List. (The API user will not note this as it happens "under the hood".)

Iterative clearing:

template<typename T>
struct Node {
    Node(): item(), next(nullptr) {}
    Node(T x): item(x), next(nullptr) {}
    T item;
    Node* next;
};

template <typename T>
struct List {
    List() : head(nullptr), tail(nullptr) {}
    ~List() { clear(); }
    Node<T>* head, tail;
    void insert(T x) {
        Node<T>* newNode = new Node<T>(x);
        if (head == nullptr) head = tail = newNode;
        else {
            tail->next = newNode;
            tail = tail->next;
        }
    }

    void clear() {
        while (head) {
            Node<T> *p = head; head = head->next;
            delete p;
        }
        tail = nullptr;
    }

    // Using the default copy ctor would corrupt the memory management.
    // Deleting it lets the compiler check for accidental usage.
    List(const List&) = delete;
    // Delete assignment operator as well.
    List& operator=(const List&) = delete;
};

Since we're not in a FP (functional programming) land I would recommend to avoid recursion (especially) for list destruction. — Mr D, Jul 29 '17 at 19:46
@user202729 There is a Q/A regarding tail call optimization: [SO: Which, if any, C++ compilers do tail-recursion optimization?](https://stackoverflow.com/q/34125/7478597). According to my above story, the compiler in VS2013 seems to lack it (as these crashing tests were made in an optimized release build). — Scheff's Cat, May 11 '18 at 07:46

Destructing a linked list

1 Answers1

Linked