Implementing a linked list in C++

Question

I am an experienced C# developer and started with C++ a few days ago. I implemented a simple linked list to play around with templates, iterators, pointers, references and stuff.

What would experienced C++ developers do differently?

Thread-safety and performance were not a priority in this implementation. I wanted it to work and to be written C++-style, not C#-style.

#include <stdint.h>
#include <iostream>

template<class T>
class LinkedList final {

public:
    LinkedList();

    LinkedList(const LinkedList<T> &src);

    LinkedList(const LinkedList<T> &&src);

    LinkedList &operator=(const LinkedList &src);

    LinkedList &operator=(const LinkedList &&src);

    void Add(const T &value);

    void Remove(std::uint32_t index);

    T Get(std::uint32_t index) const;

    void Print() const;

    std::uint32_t GetCount() const;

private:
    struct ListNode {

        ListNode(const T value) : value_(value), next_(nullptr) {
        }

        ~ListNode() {
        }

        ListNode* next_;
        T         value_;
    };

    std::uint32_t count_;
    ListNode*     start_;
    ListNode*     end_;

public:
    struct iterator {
        typedef std::forward_iterator_tag iterator_category;
        typedef T         value_type;
        typedef T*        pointer;
        typedef T&        reference;
        typedef size_t    size_type;
        typedef ptrdiff_t difference_type;

        iterator(ListNode* init = nullptr) : current_(init) {}

        T& operator*() {
            return current_->value_;
        }

        const T& operator*() const {
            return current_->value_;
        }

        iterator& operator++() { // prefix
            if (current_ != nullptr)
                current_ = current_->next_;
            return *this;
        }

        iterator operator++(int) { // postfix
            iterator temp = *this;
            ++*this;
            return temp;
        }

        bool operator==(const iterator& x) const {
            return current_ == x.current_;
        }

        bool operator!=(const iterator& x) const {
            return current_ != x.current_;
        }

    private:
        ListNode * current_;
    };

    iterator begin() {
        return iterator(start_);
    }

    iterator end() {
        return iterator();
    }
};

template<class T>
inline LinkedList<T>::LinkedList(): start_(nullptr), end_(nullptr), count_(0) {
}

template<class T>
inline LinkedList<T>::LinkedList(const LinkedList<T>& src)
    : start_(nullptr), end_(nullptr), count_(0) {
    for (auto node_iter = src.start_; node_iter != nullptr; node_iter = node_iter->next_)
    {
        Add(node_iter->value_);
    }
}

template<class T>
inline LinkedList<T>::LinkedList(const LinkedList<T>&& src) : count_(src.count_), start_(src.start_), end_(src.end_) {
}

template<class T>
inline LinkedList<T> & LinkedList<T>::operator=(const LinkedList & src) {
    auto delete_iter = start_;

    while (delete_iter != nullptr) {
        start_ = start_->next_;
        delete delete_iter;
        delete_iter = start_;
    }

    for (auto node_iter = src.start_; node_iter != nullptr; node_iter = node_iter->next_)
    {
        Add(node_iter->value_);
    }

    return *this;
}

template<class T>
inline LinkedList<T> & LinkedList<T>::operator=(const LinkedList &&src) {
    count_ = src.count_;
    start_ = src.start_;
    end_ = src.end_;

    return *this;
}

template<class T>
inline void LinkedList<T>::Add(const T &value) {
    if (start_ == nullptr) {
        start_ = new ListNode(value);
        end_ = start_;
    }
    else {
        end_->next_ = new ListNode(value);
        end_ = end_->next_;
    }

    count_++;
}

template<class T>
inline void LinkedList<T>::Remove(std::uint32_t index) {
    if (index >= count_) {
        throw std::out_of_range("Index was larger than list length.");
    }

    count_--;

    if (index == 0) {
        auto old_start = start_;
        start_ = start_->next_;
        if (count_ == 1)
            end_ = nullptr;

        delete old_start;
        return;
    }

    auto current = start_;
    while (--index > 0)
    {
        current = current->next_;
    }

    auto next = current->next_;
    current->next_ = next->next_;

    if (end_ == next) {
        end_ = current;
    }

    delete next;
}

template<class T>
inline T LinkedList<T>::Get(std::uint32_t index) const {
    if (index >= count_) {
        throw std::out_of_range("Index was larger than list length.");
    }

    auto current = start_;
    while (index-- > 0) {
        current = current->next_;
    }

    return current->value_;
}

template<class T>
inline void LinkedList<T>::Print() const {
    if (start_ == nullptr) {
        std::cout << "[empty]" << std::endl;
        return;
    }

    auto current = start_;
    while (current->next_ != nullptr)
    {
        std::cout << current->value_ << " - ";
        current = current->next_;
    }

    std::cout << current->value_ << std::endl;
}

template<class T>
inline std::uint32_t LinkedList<T>::GetCount() const {
    return count_;
}

Answer 1

Code Review

Prefer to use C++ header. This is a C-header.

#include <stdint.h>

The C++ equivalent is <cstdint>. The difference is the C version puts everything in the global namespace (and can put things in the standard namespace), while the C++ version puts everything in the standard namespace std (and can put things in the global namespace).

#include <cstdint>  // C++ headers that have an equivalent C header
                    // add a prefix `c` and drop the `.h` suffix.

When you use move semantics (and thus r-value references) you usually end up modifying the object being referenced. As a result r-value references are never const.

Also with move semantics the operations are usually exception safe so you also usually mark these functions as noexcept (unless there is a chance for an exception). This can be important if your object is placed inside a container as the standard containers can be optimized if the type they contain can be moved safely.

    // So good try on these.
    LinkedList(const LinkedList<T> &&src);
    LinkedList &operator=(const LinkedList &&src);

    // But usally they are written like this:
    LinkedList(LinkedList<T>&& src)          noexcept;
    LinkedList& operator=(LinkedList&& src)  noexcept;

Also; the easiest way to write move is via swap so you would also normally see:

    void swap(LinkedList& other) noexcept;

I also don't seem to notice a destructor here. To avoid leaks the list should understand how to release its own memory. This requires a destructor. So unless you are doing some fancy tricks (which you should not be doing) then the list is going to leak when destroyed.

This is a good standard Add (though method names usually have a lower case first letter).

    void Add(const T &value);

You pass by const reference, but to put the T into the list you need to make a copy of it. This can be inefficient if T is complex to copy (like a linked list). So there is usually two other options (in addition). An add that uses a move (rather than a copy) and an add that takes the parameters that can be used to build a T in place.

    void Add(T&& value);         // pass value by r-value reference allowing a move.
    template<typename... Args>
    void Add(Args&&... args);    // pass parameters that allow you to build a `T` in place.

The get returns by value. This means you are forcing a copy of the returned value. This is not always necessary (or desired). A copy could be expensive, also you may want to alter the object in place in the list.

    T Get(std::uint32_t index) const;


    // I would write like this:
    T const& get(std::uint32_t index) const;   // Get a const reference to the object.
    T&       get(std::uint32_t index);         // Get a reference to the object.

The const version is useful if your container is const you can still access the object and call const members on the object. The second one allows you to call methods in place on the object while it is still in the container.

Sure. Print() is a nice function to have. But printing is usually putting on the std::cout stream by default. But there are also a lot of other streams that have the same type of properties. So by all means use std::cout as the default but a print should take a the actual stream as a parameter.

    void Print() const;

    // I would write like this:
    void print(std::ostream& str = std::cout) const;

Also the standard way to print something is to use the output operator. So you should add a friend function that prints the list in the standard C++ way.

    friend std::ostream& operator<<(std::ostream& str, LinkedList const& list)
    {
        list.print(str);
        return str;
    }

If a function does nothing. Best to not add it to the code.

        ~ListNode() {
        }

It just clutters stuff up.

Ahh the fun of writing your own iterators.

    iterator begin() {
        return iterator(start_);
    }

    iterator end() {
        return iterator();
    }

There are two more you need to add:

    const_iterator begin()  const {return const_iterator(start_);}
    const_iterator cbegin() const {return const_iterator(start_);}
    const_iterator end()    const {return const_iterator();}
    const_iterator cend()   const {return const_iterator();}

First minor bug.

Your move semantics don't actually work. Rather than move you have done a shallow copy.

The problem here is that now both original and the new version point at the same list of nodes (you probably did this because you marked the parameters const and thus could not change them).

template<class T>
inline LinkedList<T>::LinkedList(const LinkedList<T>&& src) : count_(src.count_), start_(src.start_), end_(src.end_) {
}

template<class T>
inline LinkedList<T> & LinkedList<T>::operator=(const LinkedList &&src) 
{
    count_ = src.count_;
    start_ = src.start_;
    end_ = src.end_;

    return *this;
}

This causes a lot of problems when the objects are destroyed. As both objects will try and destroy the same list of nodes (its a good job you don't have a destructor as that would be bad).

But there are other side affects. If you alter one list the other list is also modified. This is probably not the expected behavior.

The best way to implement this is basically

template<class T>
inline LinkedList<T>::LinkedList(LinkedList<T>&& src) noexcept
    : count_(0)
    , start_(nullptr)
    , end_(nullptr)
{
    swap(src);
}

template<class T>
inline LinkedList<T> & LinkedList<T>::operator=(LinkedList&& src) noexcept
{
    swap(src);
    return *this;
}

template<class T>
void LinkedList<T>swap(LinkedList& other) noexcept
{
    using std::swap;
    swap(count,      other.count);
    swap(start_,     other.start_);
    swap(end_,       other.end_);
}

Second bug.

You correctly delete the original list. But you forgot to reset end_ before calling Add(). Thus you add the src list onto the end of the original list.

Assume you fix that. There is still another problem. Your technique is not exception safe. To provide the strong guarantee your methods must either work or if it fails the object must not change. The problem here is that you destroy the old state before you make a copy of the src list. Thus if the copying fails you can not get the old state back so you can't provide the strong gurantee.

template<class T>
inline LinkedList<T> & LinkedList<T>::operator=(const LinkedList & src) {
    auto delete_iter = start_;

    while (delete_iter != nullptr) {
        start_ = start_->next_;
        delete delete_iter;
        delete_iter = start_;
    }

    for (auto node_iter = src.start_; node_iter != nullptr; node_iter = node_iter->next_)
    {
        Add(node_iter->value_);
    }

    return *this;
}

There is a clever trick that makes this very simple though. Its called the copy and swap idiom. Simply stated you implement the assignment operator in terms of the copy constructor.

template<class T>
inline LinkedList<T>& LinkedList<T>::operator=(LinkedList const& src)
{
    LinkedList<T>  tmp(src);    // make a copy of the src.
    swap(tmp);                  // swap the `tmp` object and this object
    return *this;
}
// At this point `tmp` has gone out of scope.
// Thus its destructor is called. This cleans up the object and
// destroys its internal list. Note we called swap. So the tmp
// object contains this objects original content so we safely destroy it.

The above is the way you first learn.
But there is also a clever trick, that simplifies the above:

// This does exactly the same as above with one less line.
template<class T>
inline LinkedList<T>& LinkedList<T>::operator=(LinkedList src)
{
    swap(src);
    return *this;
}

There are a couple of other points around optimizing where you don't need to check ranges. But first go and re-implement after you have read the above notes. Then we can go into further optimizations.

Answer 2

Headers

With a small change (<stdint.h> → <cstdint>), we have a definition for std::uint32_t (I don't recommend this type, as it's not required to be provided - std::size_t appears more appropriate where you use it).

To correctly define std::size_t, std::ptrdiff_t, std::forward_iterator_tag and std::out_of_range, we also need

#include <cstddef>
#include <stdexcept>
#include <iterator>

You may have got away without these with your particular Standard Library implementation, but C++ says you can't rely on that.

Interface and naming

It will be easier to "drop in" this list into code in place of one of the standard containers if we use the normal naming conventions and signatures. For example, we should replace

void Add(const T &value);

void Remove(std::uint32_t index);

T Get(std::uint32_t index) const;

void Print() const;

std::uint32_t GetCount() const;

with

void push_back(const T& value);
void push_back(T&& value);
template<typename... Args>
reference emplace_back(Args&&... args);

iterator erase(const_iterator pos);

T& at(std::size_t index);
T const& at(std::size_t index) const;

friend std::ostream& operator<<(std::ostream& os, const LinkedList<T>& list);

std::size_t size() const;

Note that some of these methods come in const/non-const pairs; there's also a few other conventional methods we should consider adding (such as front(), empty(), begin(), end(), cbegin(), cend() and so on).

I've hinted in the above that we should declare some useful and conventional member types:

using value_type = T;
using size_type = std::size_t;
using difference_type = std::ptrdiff_t;
using reference = value_type&;
using const_reference = value_type const&;
using pointer = T*;
using const_pointer = T const*;
struct iterator;
struct const_iterator;

The Rule of Zero, and ownership semantics

When writing C++, we consider it good practice to manage resource ownership only in classes designed for that purpose. This separation of concerns allows most of our classes to use the compiler-generated copy constructors, assignment operators and destructors.

In our case, we can use a unique-pointer to our head node (so that's owned by the list) and a unique-pointer for each node to own its next:

#include <memory>

std::unique_ptr<ListNode> head;
ListNode *tail; // Note: this is a _non-owning_ pointer

struct ListNode
{
    std::unique_ptr<ListNode> next;
    T value;
};

Now, all our resources will be cleaned up for us when the list is destroyed, and we've reduced the amount of code we need to run under Valgrind to validate it.

Initializers

It's misleading to write

    ListNode(const T value)
        : value(value), next(nullptr)

This suggests to the reader that value will be initialized first, but that's not true, because members are initialized in order of declaration in the struct. Change either the order of these initializers or the order of the members. (In this case, it doesn't matter, but this could trip you up when an initializer expression uses the value of a different member).

We can make this structure accept both lvalues and rvalues with a single constructor, and we don't need a destructor:

struct ListNode
{
    T value;
    std::unique_ptr<ListNode> next = {};

    ListNode(value)
        : value(std::move(value))
    {
    }
};

Modified code

I've made the changes above; there's a few other changes I ought to write up properly when time permits.

#include <cstddef>
#include <initializer_list>
#include <iosfwd>
#include <iterator>
#include <memory>
#include <stdexcept>

template<class T>
class LinkedList final {

    struct ListNode
    {
        T value;
        std::unique_ptr<ListNode> next = {};

        ListNode(T value)
            : value(std::move(value))
        {
        }
    };

    std::unique_ptr<ListNode> head = {};
    ListNode *tail = {};
    std::size_t count = 0;

public:
    using value_type = T;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using reference = value_type&;
    using const_reference = value_type const&;
    using pointer = T*;
    using const_pointer = T const*;

    struct iterator {
        typedef std::forward_iterator_tag iterator_category;
        typedef T         value_type;
        typedef T*        pointer;
        typedef T&        reference;
        typedef std::size_t    size_type;
        typedef std::ptrdiff_t difference_type;

        iterator(ListNode* init = nullptr) : current(init) {}

        reference operator*() const {
            return current->value;
        }

        iterator& operator++() { // prefix
            if (current)
                current = current->next;
            return *this;
        }

        iterator operator++(int) { // postfix
            iterator temp = *this;
            if (current)
                current = current->next;
            return temp;
        }

        bool operator==(const iterator& x) const {
            return current == x.current;
        }

        bool operator!=(const iterator& x) const {
            return current != x.current;
        }

    private:
        ListNode *current;
    };

    struct const_iterator {
        typedef std::forward_iterator_tag iterator_category;
        typedef T const value_type;
        typedef T const * pointer;
        typedef T const & reference;
        typedef std::size_t    size_type;
        typedef std::ptrdiff_t difference_type;

        const_iterator(const ListNode* init = nullptr) : current(init) {}
        const_iterator(const iterator& it) : current(it.curront) {}

        reference operator*() const {
            return current->value;
        }

        const_iterator& operator++() { // prefix
            if (current)
                current = current->next.get();
            return *this;
        }

        const_iterator operator++(int) { // postfix
            iterator temp = *this;
            if (current)
                current = current->next.get();
            return temp;
        }

        bool operator==(const const_iterator& x) const {
            return current == x.current;
        }

        bool operator!=(const const_iterator& x) const {
            return current != x.current;
        }

    private:
        const ListNode *current;
    };

    LinkedList() = default;

    LinkedList(std::initializer_list<T> values) {
        for (auto v: values)
            push_back(v);
    }

    LinkedList(const LinkedList<T> &src) {
        for (auto value: src)
            push_back(value);
    }
    LinkedList(LinkedList<T> &&src) = default;

    LinkedList &operator=(const LinkedList &src) {
        return *this = LinkedList(src);
    }
    LinkedList &operator=(LinkedList &&src) = default;


    void push_back(T value) {
        tail = ((head ? tail->next : head) = std::make_unique<ListNode>(std::move(value))).get();
        ++count;
    }

    template<typename... Args>
    reference emplace_back(Args&&... args) {
        push_back(T{ args...});
        return tail->value;
    }

    iterator erase(const_iterator pos);

    T& at(std::size_t index);
    T const& at(std::size_t index) const;

    friend std::ostream& operator<<(std::ostream& os, const LinkedList& list)
    {
        if (!list.head) {
            return os << "[empty]" << std::endl;
        }

        for(auto current = list.head.get();  current;  current = current->next.get()) {
            os << current->value << " - ";
        }
        return os << '\n';
    }

    std::size_t size() const { return count; };

    iterator begin() { return iterator(head.get()); }
    const_iterator begin() const { return const_iterator(head.get()); }
    const_iterator cbegin() const { return const_iterator(head.get()); }

    iterator end() { return iterator(); }
    const_iterator end() const { return const_iterator(); }
    const_iterator cend() const { return const_iterator(); }
};


// Test Program
#include <iostream>
int main()
{
    LinkedList<int> list;
    list.push_back(42);
    list.push_back(17);

    std::cout << list << std::endl;

    LinkedList<int> other { -200, 0, 16 };
    std::cout << other.emplace_back(59) << std::endl;
    list = other;

    std::cout << list << std::endl;
}

The test program compiles without warnings (g++ -std=c++17 -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Weffc++) and executes without error under Valgrind.