My first implementation of a linked list in C++

Question

This is my very first implementation of a full-fledged ADT, which could potentially be use-ready. Now, I'm still learning, therefore I would like to ask you what I can do to further improve the following code.

#ifndef LIST_H
#define LIST_H

#include <utility>
#include <type_traits>
#include <stdexcept>
#include <assert.h>

template<typename T>
class List {
    class Node {
        friend List;

        Node *m_next;
        typename std::aligned_storage<sizeof(T), alignof(T)>::type m_data;

        Node() : m_next(nullptr) {}
        Node(const T &data, Node *next) : m_next(next) {
            new(&m_data) T(data);
        }
    };

    Node *m_sentinel,
         *m_head,
         *m_tail;

    size_t m_length;

    template<bool is_const>
    class Iterator_ {
        friend List;

        using NodeType           = typename std::conditional<is_const, const Node*, Node*>::type;
        using ValueReferenceType = typename std::conditional<is_const, const T&, T&>::type;
        NodeType m_node;

        Iterator_(NodeType node) : m_node(node) {}

        public:
            Iterator_(const List &list, size_t index = 0) : m_node(list.m_head) {
                if (index >= list.m_length) throw std::out_of_range("Iteration out of bounds");
                operator+(index);
            }

            Iterator_ &operator++() {
                assert(m_node != m_node->m_next);
                m_node = m_node->m_next;
                return *this;
            }

            Iterator_ operator++(int) {
                Iterator old = *this;
                operator++();
                return old;
            }

            Iterator_ &operator+(size_t index) {
                for (size_t cur_index = 0; cur_index < index; ++cur_index)
                    operator++();

                return *this;
            }

            bool operator==(const Iterator_ &cmp) const {
                return m_node == cmp.m_node;
            }

            bool operator!=(const Iterator_ &cmp) const {
                return !operator==(cmp);
            }

            ValueReferenceType &operator*() const {
                assert(m_node != m_node->m_next); // Dereferencing a sentinel (end iterator)
                return reinterpret_cast<ValueReferenceType>(m_node->m_data);
            }
    };

    using Iterator      = Iterator_<false>;
    using ConstIterator = Iterator_<true>;

    public:
        List() : m_sentinel(new Node()), m_head(m_sentinel), m_tail(m_sentinel), m_length(0) {}

        List(const List &copy) : List() {
            append(copy);
        }

        List(List &&move) : List() {
            std::swap(m_sentinel, move.m_sentinel);
            std::swap(m_head,     move.m_head);
            m_tail   =            move.m_tail;
            m_length =            move.m_length;
        }

        virtual ~List() {
            clear();
            delete m_sentinel;
        }

        Iterator begin() {
            return Iterator(m_head);
        }

        Iterator end() {
            return Iterator(m_sentinel);
        }

        ConstIterator begin() const {
            return ConstIterator(m_head);
        }

        ConstIterator end() const {
            return ConstIterator(m_sentinel);
        }

        ConstIterator cbegin() const {
            return ConstIterator(m_head);
        }

        ConstIterator cend() const {
            return ConstIterator(m_sentinel);
        }

        List &clear() {
            if (m_head != m_sentinel) {
                ConstIterator iter     = cbegin(),
                              iter_end = cend();

                while (iter != iter_end) {
                    const Node *node = iter.m_node;
                    ++iter;
                    delete node;
                }
            }
            m_head = m_tail = m_sentinel;
            m_length = 0;
            return *this;
        }

        List &insert(const T &element, size_t index = 0) {
            if (index > m_length) {
                assert(0);
                index = m_length;
            }

            if (!index) {
                m_head = new Node(element, m_head);
                if (!m_length) m_tail = m_head; // Our first element, that makes the tail and head the same
            } else if (index == m_length - 1) append(element);
            else {
                Node *previous = Iterator(*this, index - 1).m_node,
                     *new_node = new Node(element, previous->m_next);

                previous->m_next = new_node;
            }

            ++m_length;
            return *this;
        }

        List &append(const T &element) {
            Node *old_tail = m_tail;
            m_tail = new Node(element, m_sentinel);
            if (!m_length) m_head = m_tail; // Our first element, that makes the tail and head the same
            else old_tail->m_next = m_tail;

            ++m_length;
            return *this;
        }

        List &append(const List &copy) {
            for (const T &v : copy) append(v);
            return *this;
        }

        List &remove(size_t index) {
            if (index >= m_length) throw std::out_of_range("Removal out of bounds");

            if (!index) {
                Node *next = m_head->m_next;
                delete m_head;
                m_head = next;
            } else {
                Iterator iter(*this, index - 1);
                Node *previous = iter.m_node,
                     *rem      = previous->m_next;

                previous->m_next = rem->m_next;
                delete rem;
            }

            --m_length;
            return *this;
        }

        List &reverse() {
            if (m_length < 2) return *this;

            Node *previous = nullptr,
                 *next     = nullptr,
                 *cur      = m_head;

            while (cur != m_sentinel) {
                next = cur->m_next;

                if (cur != m_head) cur->m_next = previous;

                previous = cur;
                cur = next;
            }

            std::swap(m_head, m_tail);
            m_tail->m_next = m_sentinel;

            return *this;
        }

        bool operator==(const List &cmp) const {
            return m_head == cmp.m_head;
        }

        bool operator!=(const List &cmp) const {
            return !operator==(cmp);
        }

        T &operator[](size_t index) const {
            return *Iterator(*this, index);
        }

        List &operator=(const List &copy) {
            clear();
            append(copy);
            return *this;
        }

        size_t size() const {
            return m_length;
        }
};

#endif

Answer 1

Resource Management.

Copy the list. You have obeyed the rule of three. But you don't provide the strong exception guarantee on your copy assignment operator. Basically this means that assignment either works and you make a copy of the new list from the source into the dest, BUT if it fails then the object i sleft unchanged.

    List &operator=(const List &copy) {

        clear();         //  Here you destroy the current state.
        append(copy);    //  If this fails.
                         //  you can not reset the state of the object.
        return *this;
    }

This is called the basic exception guarantee. That's fine but you need to document it because most people expect the strong exception gurantee. Also using the copy and swap idiom mkae providing this gurantee easy,

    // Copy assignment with copy and swap.
    List& operator=(List const& rhs)
    {
        List  tmp(rhs);    // Copy:  Make  copy into a temporary.
        rhs.swap(*this);   // Swap;  (exception safe)
        return *this;
    }

Moving the list. You have the move constructor. But I am not convinced it is correct. But you also missed the move assignment operator.

    List(List &&move) : List() {
        std::swap(m_sentinel, move.m_sentinel);
        std::swap(m_head,     move.m_head);

        // Why not swap these members?
        m_tail   =            move.m_tail;
        m_length =            move.m_length;
    }

The requirement is that the object that was moved is left in a valid state (Though indeterminate). I am not convinced this is valid state. If I call methods on this object it should not cause bad things to happen (though I should not expect to know what could happen).

Currently:

 List<int>  list;
 list.append(6);

 // Some badly written function.
 // That **may** take ownership of the list but it may not.
 sendListSomewhere(std::move(list));

 // If the list was moved.
 // This will append `5` to the list that was moved
 // not to the current list.
 //
 // If the list was not moved
 // then it adds 5 to the current list locally.
 if (list.empty()) {
    list.append(5);
 }

Also the move assignment operator has not been written.

 List<int>  z;
 z = std::move(list);

Also you should mark the move operator as non throwing (by using noexcept). This will allow the standard containers to use your list in the most optimal way possible and still provide the strong exception guarantee.

std::vector<List<int>>   x;
x.puhs_back();
x.push_back();  // If List does not have an noexcept move constructor
                // then vector must fall back to using copy constructor
                // when the internal structure of x is resized.
                //
                // Alternatively if the move constructor is noexcept
                // then a resize can use the move constructor
                // and still provide the strong exception guarantee.

Sentinel

Node *m_sentinel,
     *m_head,
     *m_tail;

You don't really need head/tail if you are using a sentinel. The head is the element after the sentinel. The tail is the one before the sentinel. There is no need to keep track of these values. (Now I see you are using a singly linked list so no previous. So you will need tail (just not head).

Also don't be lazy with the declarations.

Node* m_sentinel,
Node* m_head,
Node* m_tail;

In C++ (unlike C) the * or the & tend to be placed with the type not the variable (its part of the type and the type is much more important in C++ than C).

Placement New is not needed.

 typename std::aligned_storage<sizeof(T), alignof(T)>::type m_data;
 Node(const T &data, Node *next)
     : m_next(next)
 {
     new(&m_data) T(data);
 }

I would just have written:

 T data;
 Node(Node* next, T const& data, Node* next)
      : m_next(next)
      , m_data(data)
 {}

I would also add a move version of the Node constructor.

 Node(Node* next, T&& data)
      : m_next(next)
      , m_data(std::forward<T>(data)
 {}

Also for complex types of T you should allow the object T to be built in place by forwarding the constructor arguments for T.

 template<typename... Args>
 Node(Node* next, Args...&& args)
      : m_next(next)
      , m_data(std::forward<Args>(args)...)
 {}

Hate the use of assert.
It means that production code runs and behaves differently from test code. In my opinion code should behave the same way no matter what (otherwise things become hard to diagnose when things go wrong).

            Iterator_ &operator++() {
                assert(m_node != m_node->m_next);
                m_node = m_node->m_next;
                return *this;
            }

Not sure why you are using reinterpret_cast.

            ValueReferenceType &operator*() const {
                return reinterpret_cast<ValueReferenceType>(m_node->m_data);
            }

There should be no need to use this type.

Another insert.

        List &insert(const T &element, size_t index = 0) {
            if (index > m_length) {
                assert(0);
                index = m_length;
            }

So in test code it terminates. But in production code you add it to the end of the list. That will confuse somebody one day. Throw an exception....

Insert should not be that hard. The point of using the sentinel is to make the need for testing for empty list irelavant.

   List& insert(T const& element, std::size_t index = 0)
   {
       if (index > m_length) {
           throw XXX("XXXX");
       }

       Node*  mark = sentinel;
       while(index != 0) {
           --index;
           mark = mark->m_next;
       }


       // Deliberately not updating m_head as it is always
       // the one after the sentinel (so I am not storing it).


       mark->m_next = new Node(mark->m_next, element);
       return *this;
   }
       

Same thing with the append. You don't need to check the size.

        List &append(const T &element) {
            Node *old_tail = m_tail;
            m_tail = new Node(element, m_sentinel);
            if (!m_length) m_head = m_tail; // Our first element, that makes the tail and head the same
            else old_tail->m_next = m_tail;

            ++m_length;
            return *this;
        }

        // This is what I would do.
        List& append(T const& element)
        {
            m_tail->m_next = new Node(m_sentinel, element);
            m_tail = m_tail->m_next;

            // Deliberately not updating m_head as it is always
            // the one after the sentinel (so I am not storing it).

            ++m_length;
            return *this;
        }

Same thing with the remove. You don't need to check the size.

        List& remove(size_t index)
        {
            if (index >= m_length) {
                throw std::out_of_range("Removal out of bounds");
            }

           Node*  mark = sentinel;
           while(index != 0) {
               --index;
               mark = mark->m_next;
           }

           old = mark->m_next;
           mark-m_next = old->m_next;
           --m_length;

           delete old;
           return *this;
        }

Comparison.

This test to see if it is the same objext. It does not test to see if the list contain the same elements. I would expect the latter.

        bool operator==(const List &cmp) const {
            return m_head == cmp.m_head;
        }

I would do it like this:

Note: this compiles and works on the one test I tried.
But it has not been code reviewed or tested in any meaningful way and thus is liable to contain errors.

namespace ThrosAnvil
{

    template<typename T>
    class LinkedList
    {
        struct Node
        {
            Node(Node* prev, Node* next)
                : prev(prev)
                , next(next)
            {
                prev->next = this;
                next->prev = this;
            }
            virtual ~Node() {}
    
            Node*       next;
            Node*       prev;
        };
        struct DataNode: public Node
        {
            DataNode(Node* prev, Node* next, T const& data)
                : Node(prev, next)
                , data(data)
            {}
            DataNode(Node* prev, Node* next, T&& data)
                : Node(prev, next)
                , data(std::forward<T>(data))
            {}
            template<typename... Args>
            DataNode(Node* prev, Node* next, Args&& ...args)
                : Node(prev, next)
                , data(std::forward<Args>(args)...)
            {}
            T           data;
        };
    
        Node    sentinel;
    
            template<typename ResultType>
            struct IteratorBase
            {
                Node* current;
                IteratorBase(Node* node)
                    : current(node)
                {}
                bool operator==(IteratorBase const& rhs) const      {return current == rhs.current;}
                bool operator!=(IteratorBase const& rhs) const      {return !(*this == rhs);}
    
                IteratorBase& operator++()                          {current = current->next;return *this;}
                IteratorBase& operator--()                          {current = current->prev;return *this;}
                IteratorBase  operator++(int)                       {IteratorBase result(*this); ++(*this);return result;}
                IteratorBase  operator--(int)                       {IteratorBase result(*this); --(*this);return result;}
    
                ResultType& operator*() const                       {return static_cast<DataNode*>(current)->data;}
                ResultType* operator->() const                      {return &static_cast<DataNode*>(current)->data;}
            };
        public:
            using iterator          = IteratorBase<T>;
            using const_iterator    = IteratorBase<T const>;
    
            // Default
            LinkedList()
                : sentinel(&sentinel, &sentinel)
            {}
            // Copying␣
            LinkedList(LinkedList const& copy)
                : LinkedList()
            {
                for(auto const& val: copy) {
                    push_back(val);
                }
            }
            LinkedList& operator=(LinkedList const& rhs)
            {
                LinkedList      tmp(rhs);
                tmp.swap(*this);
                return *this;
            }
            // Moving
            LinkedList(LinkedList&& move) noexcept
                : LinkedList()
            {
                move.swap(*this);
            }
            LinkedList& operator=(LinkedList&& rhs) noexcept
            {
                rhs.swap(*this);
                return *this;
            }
            // Destroying
            ~LinkedList()
            {
                Node* next;
                for(Node* loop = sentinel.next; loop != &sentinel; loop = next)
                {
                    next = loop->next;
                    delete loop;
                }
            }
            // Swap
            void swap(LinkedList& other) noexcept
            {
                using std::swap;
                swap(sentinel.next->prev, other.sentinel.next->prev);
                swap(sentinel.prev->next, other.sentinel.prev->next);
                swap(sentinel.next, other.sentinel.next);
                swap(sentinel.prev, other.sentinel.prev);
            }
    
            // Copying value into list
            void push_back(T const& value)      {new DataNode(sentinel.prev, &sentinel, value);}
            void push_front(T const& value)     {new DataNode(&sentinel, sentinel.next, value);}
    
            // Moving value into list
            void push_back(T&& value)           {new DataNode(sentinel.prev, &sentinel, std::forward<T>(value));}
            void push_front(T&& value)          {new DataNode(&sentinel, sentinel.next, std::forward<T>(value));}
    
            // Emplaning value into list
            template<typename... Args>
            void emplace_back(Args&& ...args)   {new DataNode(sentinel.prev, &sentinel, std::forward<Args>(args)...);}
            template<typename... Args>
            void emplace_front(Args&& ...args)  {new DataNode(&sentinel, sentinel.next, std::forward<Args>(args)...);}
    
    
            iterator begin()                    {return iterator(sentinel.next);}
            iterator end()                      {return iterator(&sentinel);}
            const_iterator begin()  const       {return const_iterator(sentinel.next);}
            const_iterator end()    const       {return const_iterator(&sentinel);}
            const_iterator cbegin() const       {return const_iterator(sentinel.next);}
            const_iterator cend()   const       {return const_iterator(&sentinel);}
    };
    
    template<typename T>
    void swap(LinkedList<T>& lhs, LinkedList<T>& rhs)
    {
        lhs.swap(rhs);
    }
}