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?

• Toby Speight: Since you have tagged memory-management, it's worth mentioning how you tested - have you exercised your code under Valgrind or similar?
• JDługosz: Just a short note not worth a whole reply: Your Delete also contains the Find logic. You should make that common code.

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.

• Davislor: Respectfully disagree on the advice that we should avoid tail-recursion because C++ doesn’t formally "mandate" tail-call optimization. Every significant compiler has done it, for decades. If you care about optimization, and you’re using a compiler that doesn’t even do that, the tool you are using does not meet your requirements.
• Deduplicator: @Davislor One can care about efficiency, but still prefer working code for non-optimizing or badly optimizing implementations.
• Davislor: @Deduplicator Is there a compiler in wide use that doesn’t do this optimization on production code, or is this like, the standard doesn’t formally require two’s-complement arithmetic or an ASCII-compatible character set?
• Deduplicator: @Davislor The most widely used compiler-option resulting in that is using none at all, I think. While requiring two's complement is reasonable enough for most of us if it simplifies things, requiring ASCII+ has more pitfalls.
• Deduplicator: @Davislor Slow isn't the problem. Tail-calls not being optimized, thus making stackframes pile up, and causing a stack overflow, is.

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;
}

• JDługosz: re "breathe": The top one is better, but still noisy. Eliminate the else keywords (eliminate the second by reversing the condition) and the redundant braces.

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 LinkedListNode(value, nullptr);
 tail = tail->next;
 }
 else
 {
 head = new LinkedListNode(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.

• Toby Speight: Good advice, and I usually find it's even better if we make the Node class private to LinkedList - that provides namespacing and reduces the likelihood of the implementation details leaking out.

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;
 ...
};

• Ismael Miguel: I disagree with the first part of your answer. The comments provided for the functions are basically an interpretation of what the code does, but written in English. However, it does show that the Add method could probably have a better name, like Append (since it adds to the end). This way, you can implement method like Prepend (add to the top) and Insert (add the value before m_next) - or the "classic" Push/Pop. Assuming those are possible to implement. Otherwise, Add may be a good name. The smart pointer seems to be a really good idea, and you get my upvote for that.