5
\$\begingroup\$

In order to learn C++11, I propose to myself implement a simple single linked list using smart pointers. The idea was to cover the basic operations without leave any memory leak.

I came up with a solution but I'm sure that it could be improved in many ways. So, I would like to receive feedback of any kind: format, readability, implementation, etc.

Also, I would like to hear your opinion about which is the correct way of iterate over a sequence of objects using smart pointers. After reading and looking for examples, I believe that it should be done using the get method (from the smart pointer) to obtain a raw pointer, which can be used to go through the sequence. Is there another way of doing it?.

And finally, what else could I add to the class or what do you think that is missing that I should add? I will use the answer for this question as an opportunity to keep improving/learning, so every answer is welcome.

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

#include <iostream>
#include <memory>

template <typename T>
class LinkedList
{
private:
    /* Node definition */
    class Node
    {
        friend class LinkedList<T>;        
    private:
        const T key_;
        std::unique_ptr<Node> next_;
    public:
        Node(const T k): key_{k}, next_{nullptr} {}
        ~Node() = default;
        // Commented lines: just for debuging purposes.
        // Node(const T k): key_{k}, next_{nullptr} { std::cout << "[DEBUG] Node created! (" << key_ << ")" << std::endl; }
        // ~Node(){ std::cout << "[DEBUG] Node destroyed! (" << key_ << ")" << std::endl; }

    };
    /* End node definition */
    int size_;
    std::unique_ptr<Node> head_;

public:
    LinkedList() = default;
    ~LinkedList() = default;
    //~LinkedList(){ std::cout << "[DEBUG] List destroyed!" << std::endl; }
    // Returns the key of the node at the back of the list.
    T back();
    // Returns the key of the node at index position.
    T at(unsigned int index);
    // Returns the key of the node at the front of the list.
    T front();
    // Check if the list is empty. Returns true or false.
    bool is_empty() const;
    // Removes the node of the back of the list and returns its key.
    T pop_back();
    // Removes the node of the front of the list and returns its key.
    T pop_front();
    // Returns and ostream with the keys of everynode (use with cout to print them all).
    std::ostream & print(std::ostream &os);
    // Insert a node at the front of the list.
    void push_front(const T &key);
    // Insert a node at the end of the list.
    void push_back(const T &key);
};

template<typename T>
T LinkedList<T>::at(unsigned int index)
{
    auto ptr = head_.get();
    while (--index)
        ptr = ptr->next_.get();
    return ptr->key_;
}

template<typename T>
bool LinkedList<T>::is_empty() const
{    
    return head_ == nullptr;
}

template<typename T>
T LinkedList<T>::pop_back()
{
    // This method does not handle the empty list case.
    auto prev_ptr = head_.get();
    auto curr_ptr = prev_ptr;
    while (curr_ptr->next_)
    {
        prev_ptr = curr_ptr;
        curr_ptr = curr_ptr->next_.get();
    }
    size_--;
    if (prev_ptr == curr_ptr) // head_ points to the last item.
    {    
        auto tmp = std::move(head_);
        return tmp->key_;
    }
    else
    {
        auto tmp = std::move(prev_ptr->next_);
        return tmp->key_;
    }
}

template<typename T>
T LinkedList<T>::pop_front()
{
    // This method does not handle the empty list case.
    auto ptr = std::move(head_);
    head_ = std::move(ptr->next_);
    size_--;
    return ptr->key_;
}

template<typename T>
void LinkedList<T>::push_back(const T &key)
{
    if (!head_)
        head_.reset(new Node(key));
    else
    {
        auto ptr = head_.get();
        while (ptr->next_)
            ptr = ptr->next_.get();
        ptr->next_.reset(new Node(key));
    }
    size_++;
}

template<typename T>
void LinkedList<T>::push_front(const T &key)
{
    std::unique_ptr<Node> p(new Node(key));
    p->next_ = std::move(head_);
    head_ = std::move(p);
    size_++;
}

template<typename T>
std::ostream & LinkedList<T>::print(std::ostream &os = std::cout)
{
    auto current = head_.get();
    while (current)
    {
        os << current->key_ << " ";
        current = current->next_.get();
    }
    return os << std::endl;
}

#endif
\$\endgroup\$
  • \$\begingroup\$ The pointers in a linked list do not represent ownership of memory. They simply point to the next node in the list and that node could have been allocated on the stack or the heap. \$\endgroup\$ – twohundredping May 8 '15 at 21:50
  • \$\begingroup\$ Yeah. I guess you are right about the ownership, but in the other hand, doesn't it make sense if you look at it from the memory allocation perspective?. Couldn't it be a good way to avoid memory leaks, because there is no need to call deletes to clean/remove the objects created with new (I would use make_unique if I could in C++11). Also, from what I have read, this approach (using smart pointers) is exception safe, isn't it? \$\endgroup\$ – rcanepa May 9 '15 at 0:46
  • \$\begingroup\$ @twohundredping In this case, though, the list does seem to own the pointers. They're all dynamically allocated, so deallocation is a good thing :) and the API doesn't provide ways to stick one's own Node in there, or expose the fact that such things even exist. \$\endgroup\$ – cHao May 9 '15 at 1:46
  • \$\begingroup\$ First question: is about deletion & insertion. Since the next node i.e. node C (and all nodes after that) is contained inside that node C. So, if it happens that you delete node C, all nodes will be deleted. That's the problem of using smart pointer. Does anyone know how to solve this issue? thanks \$\endgroup\$ – user105349 May 13 '16 at 11:04
4
\$\begingroup\$

Overall, it looks pretty good. A few design point I'd like to add:

  1. Have you considered making it an intrusive list instead? There isn't much use for your list class, besides the learning process of writing one, when the standard provides std::list and std::forward_list templates, however, a templated intrusive list class can have quite a few uses, and such class is not provided by the standard (thought Boost do provide an intrusive list template). Nevertheless, if you'd like to read on the topic, here are a couple references from Google:

  2. Your push_back() method could be made to run in constant time if you keep an extra reference to the list's tail. Right now, any insertion after the first one will require a full traversal of the list to find the tail. If instead you keep a valid reference to the current list tail at every new insertion, then the loop can be replaced by a cheap pointer swapping.

  3. Since Node is already an internal private class inside LinkedList, it seems a bit of overkill making it a class and then friending list with it. Node could very well be a struct or a class with all fields public.


Looking at the current code you have, there are a few minor details that stand out to me:

  1. You are keeping track of the list size/item-count, but the interface is missing a method to query its current size/count.

  2. You should explicitly initialize size_ to zero and head_ to null either directly in the declaration (allowed by C++11) or in the constructor's initializer list. Don't leave room for misunderstandings. Some things are better if explicit.

  3. Your at() method doesn't do bounds checking. If index goes beyond the size_, you will eventually try to access a null pointer and crash. You should at least validate that index is < size_ with an assertion. Or throw an exception if you prefer permanent range checking.

  4. Since front(), back() and at() are returning copies of the stored values, you should also mark them with const. print() is also just reading data from the structure, so it is naturally a const method as well. By the way, you didn't provide an implementation for front() and back(). Even tough I can have an idea about how they'd look...

  5. Instead of returning by value in methods like at() & friends and always creating a copy of the stored item, consider providing two versions of the methods, one returning a mutable reference (T&) and one returning a const reference (const T&). This can be an important optimization when storing large objects. Many times the caller only wants to look at a value, so creating a copy all the time can be detrimental to performance. Also, by always returning by value, a method like at() cannot be used to mutate the stored item. E.g. something like list_of_ints.at(5) = 42; would not change the value stored at 5. If you intend to allow this idiom, then an overload returning by reference is necessary.

  6. Like you have noted in the comments, pop_front() and pop_back() will crash for an empty list. I would still recommend at least an assert to help debugging. Remember that assertions can be disabled, so they will cost you nothing if you disable them. Use a runtime exception if you prefere having the check always there.

  7. I'd contend that the C++ world is divided between programmers that prefer printing things with a plain function/method call and those that prefer to use the stream operators. You should provide both to appease all the factions ;). The stream operator can be implemented in terms of print() so it will only be a couple extra lines of code.

  8. Instead of having commented-out code for your debug prints, you could define a simple wrapper macro for cout that can be disabled/enabled via your build system, without having to change the source code. This is one of the legitimate uses for a macro in C++, IMHO.

    #define MY_DEBUG_LOG(message) do { std::cout << "[DEBUG]: " << message << "\n"; } while (0)
    
  9. Lastly, you should get a StackExchange badge just for not using namespace std; in your code :P.

\$\endgroup\$
  • \$\begingroup\$ I really appreciate the time you took to analyze my code and provide this insightful comments. This was what I was looking for, a lot of feedback to open new paths in my learning journey! Anyway, I have just one question regarding point 5. How should I provide two versions of the method?, should I implement two different methods using differents names or overloading by return type (I'm not sure if this is possible... I read some posts in stackoverflow but it wasn't clear for me if doing that is the best way). Thanks! \$\endgroup\$ – rcanepa May 9 '15 at 17:33
  • 1
    \$\begingroup\$ Hi @rcanepa, unfortunately you can't overload a function just by return type, however, in a class method, making it const counts as a valid overload. So you would have to declare one returning ref and non-const and one returning const ref and being const. Best example is probably std::vector::at(). \$\endgroup\$ – glampert May 9 '15 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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