6
\$\begingroup\$

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?

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Since you have tagged memory-management, it's worth mentioning how you tested - have you exercised your code under Valgrind or similar? \$\endgroup\$ Jan 9, 2022 at 14:20
  • 1
    \$\begingroup\$ Just a short note not worth a whole reply: Your Delete also contains the Find logic. You should make that common code. \$\endgroup\$
    – JDługosz
    Jan 10, 2022 at 15:15

4 Answers 4

5
\$\begingroup\$
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.

\$\endgroup\$
10
  • \$\begingroup\$ 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. \$\endgroup\$
    – Davislor
    Jan 10, 2022 at 1:03
  • \$\begingroup\$ @Davislor One can care about efficiency, but still prefer working code for non-optimizing or badly optimizing implementations. \$\endgroup\$ Jan 11, 2022 at 1:02
  • \$\begingroup\$ @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? \$\endgroup\$
    – Davislor
    Jan 11, 2022 at 2:16
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Jan 11, 2022 at 2:37
  • 1
    \$\begingroup\$ @Davislor Slow isn't the problem. Tail-calls not being optimized, thus making stackframes pile up, and causing a stack overflow, is. \$\endgroup\$ Jan 11, 2022 at 3:29
5
\$\begingroup\$

#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;
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – JDługosz
    Jan 10, 2022 at 15:13
4
\$\begingroup\$

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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ Jan 10, 2022 at 8:22
0
\$\begingroup\$

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;
    …
};
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Jan 10, 2022 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.