Recommendations on improving my built-in linked list garbage collection

Question

I'm currently learning about linked lists, and I'm building one myself in C++ in order to fully grasp the concept. Every method seems to work. However, I'm not confident in my implemented garbage collection of my Node class and LinkedList class. Can anyone look at it and give any suggestions for improval? Thank you!

#include <iostream>
#include <vector>
#include <map>

template<class T>
struct Node
{
    T value;
    Node* next;

    Node() {
        next = nullptr; // Set the default of next to nullptr
    }
    ~Node() {
        if (next) {
            delete next;
            next = nullptr;
        }
    }
};

template<class T>
class LinkedList
{
private:
    Node<T>* head;
    Node<T>* tail;
    unsigned int length;

    Node<T>* traverseToIndex(const unsigned short& index);
public:
    LinkedList();
    ~LinkedList();
    void append(const T& value);
    void prepend(const T& value);
    void insert(const unsigned short& index, const T& value);
    void remove(const unsigned short& index);
};

int main()
{
    LinkedList<int> nums;
    nums.append(5);
    nums.append(1);
    nums.append(3);
    nums.append(4);
    nums.remove(2);

    return 0;
}

template<class T>
LinkedList<T>::LinkedList()
{
    this->length = 0;
    head = new Node<T>;
    tail = head;
}

template<class T>
LinkedList<T>::~LinkedList()
{
    delete head;
}

template<class T>
Node<T>* LinkedList<T>::traverseToIndex(const unsigned short& index)
{
    if (index >= this->length) return tail;

    Node<T>* currentNode = head;
    for (unsigned short i = 0; i < index; i++) {
        currentNode = currentNode->next;
    }
    return currentNode;
}

template<class T>
void LinkedList<T>::append(const T& value)
{
    if (length == 0) {
        head->value = value;
    } else {
        Node<T>* newNode = new Node<T>;
        newNode->value = value;
        tail->next = newNode;
        tail = newNode;
    }
    length++;
}

template<class T>
void LinkedList<T>::prepend(const T& value)
{
    Node<T>* newNode = new Node<T>;
    newNode->value = value;
    newNode->next = head;
    head = newNode;
}

template<class T>
void LinkedList<T>::insert(const unsigned short& index, const T& value)
{
    if (index >= this->length || index <= 0) return;

    Node<T>* before = this->traverseToIndex(index - 1);
    Node<T>* after = before->next;

    Node<T>* newNode = new Node<T>;
    newNode->value = value;
    newNode->next = after;

    before->next = newNode;

    this->length++;
}

template<class T>
void LinkedList<T>::remove(const unsigned short& index)
{
    Node<T>* before = this->traverseToIndex(index - 1);
    Node<T>* deletedNode = before->next;
    Node<T>* after = deletedNode->next;
    before->next = after;

    this->length--;
}

Questions asking for improvements to otherwise working code are better suited on [codereview.se] — jmoerdyk, Sep 03 '19 at 17:00
`remove` doesn't delete nodes. you also need to read https://stackoverflow.com/questions/4172722/what-is-the-rule-of-three — Alan Birtles, Sep 03 '19 at 17:32
This doesn't address the question, but that `Node` destructor does far more than it needs to. It's okay to delete a null pointer, so the test `if (next) is pointless. And setting `next` to `nullptr` is equally pointless, since the object is going away and its `next` member will no longer exist. Just change it to `delete next;`. — Pete Becker, Sep 03 '19 at 18:05

score 2 · Answer 1 · answered Sep 03 '19 at 17:00

~Node() {
    if (next) {
        delete next;
        next = nullptr;
    }
}

For a sufficiently long list causes stack overflow due to recursive calls to ~Node() in delete next;.

A fix is to have no destructor in Node. The destructor of LinkedList should walk the list in a loop and destroy the nodes.

Recommendations on improving my built-in linked list garbage collection

1 Answers1