Simple Singly-Linked List class

Question

Decided to write something simple and came up with idea to write simple single linked list in C++ to improve my knowledge about pointers and memory management in C++, and wrote this:

#include <iostream>

void pause() {
    std::cout << '\n' << "Press <Enter> to continue...";
    std::cin.clear();
    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
    //std::cin.get(); // Use when not debug
} // PAUSE

namespace LinkedList {

    class LinkedList {
    private:
        int m_value{};
        LinkedList* m_next{ nullptr };
    public:
        LinkedList(int value = 0) : m_value{ value } {}
        void Add(int value) {
            if (!m_next) { m_next = new LinkedList{ value }; } // If it's the last element then add
            else { m_next->Add(value); } // And if not go up in linked list
        }
        void Delete(int value) {
            if (m_next->m_value == value) { 
                LinkedList* tmp_ptr{ m_next->m_next };
                delete m_next; m_next = tmp_ptr; return; 
            } // If next value equals the value to delete then redirect the current element to element, after that, we search for
            if (!m_next) { return; } // If no element after, return
            else { m_next->Delete(value); } // If we can go upper, go

        }
        LinkedList* Find(int value) {
            if (m_value == value) { return this; } // If found return pointer to it
            else if (m_next) { m_next->Find(value); } // If still can go up, go
            else { return nullptr; } // If not found and nowhere to go up return nullptr
        } // Return a pointer to element which contains certain number
        friend std::ostream& operator<<(std::ostream& os, LinkedList list);
    };

    std::ostream& operator<<(std::ostream& os, LinkedList element) {
        while (true) {
            os << element.m_value << " ";
            if (!element.m_next) { return os; } // If it's a last element then return
            else { element = *element.m_next; } // If not go up
        }
    }

}
int main() {
    LinkedList::LinkedList test{ };
    int input{};
    while (std::cin >> input) { test.Add(input); } // Ask for input until cin fails
    std::cout << test;
    pause();
    return 0;
}

Is this any good or it could have been written better?

Answer 1

class LinkedList {
private:
    LinkedList* m_next{ nullptr };

This raw-pointer data member needs some care. We need to ensure that the memory is correctly released in the destructor, and dealt with carefully in the copy and assignment methods. I see no such care in this class, and expect to see memory leakage and/or double-free bugs until that's fixed.

---

We can simplify the while loop in the operator <<. Instead of while (true) with a break inside, we can make it easier to read by using a real condition:

friend std::ostream& operator<<(std::ostream& os, const LinkedList& element) {
    for (auto *e = &element;  e;  e = e->next) {
        os << e->m_value << " ";
    }
    return os;
}

Notice that here we pass a reference to a const element, rather than a value. We should also have a const version of Find(), so we can work with read-only objects.

---

A few of the member functions traverse the list using recursion. This can be problematic, because long lists may lead to stack overflow (C++ doesn't mandate tail-call elimination). Prefer to iterate over the list for these operations.

Answer 2

#include your stuff

On my platform, e.g. <limits> is not implicitly included. Always explicitly include all used units.

Comment, what needs clarification

Do not comment what your code does. This is clear to anybody who understands C++. Comment why your codes does stuff, if and only if it is not obvious. All of your comments are uselessly cluttering the code.

Let the code breathe

This one is kind of opinionated, but I don't like it when the code is needlessly compressed. Consider this:

if (m_value == value) { return this; }
else if (m_next) { m_next->Find(value); }
else { return nullptr; }

versus this:

if (m_value == value) {
    return this;
} else if (m_next) {
    m_next->Find(value);
} else {
    return nullptr;
}

Possible bugs

I think you intended recursion on LinkedList::Find()

if (m_value == value) {
    return this;
} else if (m_next) {
    return m_next->Find(value);  // Actually return the value of the recursive call.
} else {
    return nullptr;
}

Answer 3

When you write a container, there are two concepts to consider: the container and what goes in the container. It can be much simpler to separate these concepts in your code--for example, into separate classes. I find it easier to reason about a container as a separate entity rather than holding on to one item in the container and manipulating the rest of the collection through that one item. It's the difference between trying to carry a chain by holding on to one link versus winding the whole chain around a spool and carrying the spool. Sure, the spool adds weight, but the savings in effort make it worth it.

To see how to make a spool, let's separate your class into two classes LinkedList and LinkedListNode.

struct LinkedListNode
{
    int value;
    LinkedListNode* next;
    LinkedListNode(int new_value, LinkListNode* new_next) : value(new_value), next(new_next) {}
}

class LinkedList
{
    private:
        LinkedListNode* head;
        LinkedListNode* tail;


    public:
        LinkedList() : head(nullptr), tail(nullptr) {}
        void add(int value);
        LinkedListNode* find(int value);
}

At a cost of a single extra pointer, we can now have an add method that does not need to search for the end of the list.

void LinkedList::add(int value)
{
    if(head)
    {
        tail->next = new LinkedList(value, nullptr);
        tail = tail->next;
    }
    else
    {
        head = new LinkedList(value, nullptr);
        tail = head;
    }
}

This also allows for other methods like find() to be written as loops instead of recursion. If a LinkedList has 1,000,000 elements and the compiler doesn't happen to optimize the recursive calls into loops, your program will crash with a stack overflow error. One way to do this would be

LinkedListNode* LinkedList::find(int value)
{
    for(LinkedListNode* node = head; node; node = node->next)
    {
        if(node->value == value)
        {
            return node;
        }
    }
    return nullptr;
}

I'm not saying recursion is bad. Sometimes a recursive algorithm is easier to reason about; sometimes a looping algorithm is easier. These separated classes give you the option to implement either as needed.

Answer 4

Adding comments describing what each method does would be helpful:

// Adds a value to the tail of the linked list
void Add(int value) {
    …
}
// Removes a value from the linked list
void Delete(int value) {
    …
}
// Returns a pointer to the node containing the value
LinkedList* Find(int value) {
    …
}

Note that the Find method seems a bit verbose, I would expect a find method to return a boolean instead.

Also, consider using smart pointers to eliminate memory related issues:

#include <memory> // std::unique_ptr

class LinkedList
{
private:
    std::unique_ptr<LinkedList> _next;
    …
};