Linked list implementation C++

Question

I hope this is the right way of doing things: I've previously posted a request for a code review and gotten feedback. Now I have new improved code that I would like a code review on again. Old: C++ linked list iterator implementation

---

Known issues:

• Sentinel node contains a value
• I haven't yet learned how to implement rule of five.
• I don't understand the point of const_iterator

---

Node.h

#pragma once

namespace Util
{
    template<typename T>
    class Node
    {
    public:
        template<typename T> friend class Iterator;
        template<typename T> friend class List;
    private:
        Node(T);
        ~Node();

        void push_back(Node*);
        void unlink();

        T value;
        Node<T>* next;
        Node<T>* prev;
    };

    template<typename T>
    Node<T>::Node(T t) : value(t), next(this), prev(this)
    {
        // ...
    }

    template<typename T>
    Node<T>::~Node()
    {
        unlink();
    }

    template<typename T>
    void Node<T>::push_back(Node* n)
    {
        n->next = this;
        n->prev = prev;
        prev->next = n;
        prev = n;
    }

    template<typename T>
    void Node<T>::unlink()
    {
        next->prev = prev;
        prev->next = next;
        next = this;
        prev = this;
    }
}

---

Iterator.h

#pragma once

#include "Node.h"

namespace Util
{
    template<typename T>
    class Iterator
    {
    public:
        template<typename T> friend class List;

        T& operator*() const;
        Iterator& operator++();
        Iterator& operator--();
        Iterator& operator++(int);
        Iterator& operator--(int);
        bool operator==(const Iterator& rhs) const;
        bool operator!=(const Iterator& rhs) const;
    private:
        Iterator(Node<T>* n);
        Node<T>* node;
    };
    template<typename T>
    Iterator<T>::Iterator(Node<T>* n) : node(n)
    {
        // ...
    }

    template<typename T>
    T& Iterator<T>::operator*() const
    {
        return node->value;
    }

    template<typename T>
    Iterator<T>& Iterator<T>::operator++()
    {
        node = node->next;
        return *this;
    }

    template<typename T>
    Iterator<T>& Iterator<T>::operator--()
    {
        node = node->prev;
        return *this;
    }

    template<typename T>
    Iterator<T>& Iterator<T>::operator++(int)
    {
        Iterator<T> it(*this);
        operator++();
        return it;
    }

    template<typename T>
    Iterator<T>& Iterator<T>::operator--(int)
    {
        Iterator<T> it(*this);
        operator--();
        return it;
    }

    template<typename T>
    bool Iterator<T>::operator==(const Iterator& rhs) const
    {
        return node == rhs.node;
    }

    template<typename T>
    bool Iterator<T>::operator!=(const Iterator& rhs) const
    {
        return node != rhs.node;
    }
}

---

List.h

#pragma once

#include "Iterator.h"

namespace Util
{
    template<typename T>
    class List
    {
    public:
        typedef Iterator<T> Iterator;
        typedef Node<T> Node;

        List();
        ~List();
        List(const List&) = delete;
        List(List&&) = delete;
        List& operator=(const List&) = delete;
        List& operator=(List&&) = delete;

        // Capacity
        bool empty() const;
        int size() const;

        // Modifiers
        void push_back(const T&);
        void push_front(const T&);
        void pop_back();
        void pop_front();
        void clear();
        Iterator insert(Iterator it, const T&);
        Iterator erase(Iterator it);

        // Element access
        T& front() const;
        T& back() const;
        Iterator begin() const;
        Iterator end() const;
    private:
        Node* head;
        int list_size;
    };

    template<typename T>
    List<T>::List() : head(new Node(0)), list_size(0)
    {
        // ...
    }

    template<typename T>
    List<T>::~List()
    {
        while (!empty())
        {
            pop_back();
        }
        delete head;
    }

    template<typename T>
    bool List<T>::empty() const
    {
        return head->next == head;
    }

    template<typename T>
    int List<T>::size() const
    {
        return list_size;
    }

    template<typename T>
    void List<T>::push_back(const T& t)
    {
        head->push_back(new Node(t));
        ++list_size;
    }

    template<typename T>
    void List<T>::push_front(const T& t)
    {
        head->next->push_back(new Node(t));
        ++list_size;
    }

    template<typename T>
    void List<T>::pop_back()
    {
        delete head->prev;
        --list_size;
    }

    template<typename T>
    void List<T>::pop_front()
    {
        delete head->next;
        --list_size;
    }

    template<typename T>
    void List<T>::clear()
    {
        Iterator it = begin();
        while (!empty())
        {
            it = erase(it);
        }
    }

    template<typename T>
    typename List<T>::Iterator List<T>::insert(Iterator it, const T& t)
    {
        it.node->push_back(new Node(t));
        ++list_size;
        --it;
        return Iterator(it);
    }

    template<typename T>
    typename List<T>::Iterator List<T>::erase(Iterator it)
    {
        Node* n = it.node->next;
        delete it.node;
        --list_size;
        return Iterator(n);
    }

    template<typename T>
    T& List<T>::front() const
    {
        return head->next->value;
    }

    template<typename T>
    T& List<T>::back() const
    {
        return head->prev->value;
    }

    template<typename T>
    typename List<T>::Iterator List<T>::begin() const
    {
        return Iterator(head->next);
    }

    template<typename T>
    typename List<T>::Iterator List<T>::end() const
    {
        return Iterator(head);
    }
}

---

Possible bug: I've manually compared most of the methods of std::list and my list, and it seems coherent. Except for:

for (auto it = list.begin(); it != list.end(); ++it)
{
    it = list.erase(it);
}

The std::list deletes the all the elements and then errors because you cannot increment past it.end(). But my list deletes every other element in a weird way, and I think loops around several times.

Answer 1

1. Is there any use to only including one of the headers? No.
   Are they all part of an intrinsic whole? Yes.
   So, why try to artificially separate them? Doing so just creates extra complexity.

2. You are right that having the root store a spurious element is a serious error, especially as you might not even be able to construct it. Fortunately, that's easily remedied:
   Introduce an additional type only storing the links, have Node inherit from it, and only store that for manipulating the hierarchy.

   struct Links {
       Links* next = nullptr;
       Links* prev = nullptr;
   };
   

   For bonus points, make List::List() noexcept by making the root part of the List.

3. Node tries to do far too much. It is an implementation-detail of the list, and any desperate struggle to OO-ify, encapsulate, and make it its own separate abstraction just adds needless complexity. Yes, it needs the links (prev and next), and has to store the payload (value), but the only useful addition aside from that is a ctor forwarding all arguments to the value-member, to insulate the list from changes in the members order and prepare for implementing emplace-functions.

   All the logic belongs in the list directly.

   template <class T>
   struct Node : Links {
       template <class... X, decltype(new T(std::declval<X>(x)...))>
       Node(X&&... x) : value(std::forward<X>(x)...) {}
   
       T value;
   };
   

4. Reference-types and pointer-types are the exception, not the rule. All other user-defined types are expected to provide transitive-const. Which explains why you couldn't find much use to const_iterator.

   When re-doing all involved parts, consider using Node<std::remove_const_t<T>> for the node-type of List<T> and Iterator<T>. Doing so allows more re-use and composition.

   Also keep in mind that any iterator should be trivially convertible to the corresponding constant iterator. And that (nearly) all iterators are so light-weight passing by reference is a pessimisation.

5. If you add support for swapping (friend void swap(List& a, List& b) noexcept) and construction from arbitrary iterator-ranges (template <class InputIt> List(InputIt first, InputIt last)), the rest will easily fall into place.

6. Consider whether defining a function in-class won't simplify things.

Answer 2

• The bug in

  for (auto it = list.begin(); it != list.end(); ++it)
  {
      it = list.erase(it);
  }
  

  is due to ++it. You don't need to manually advance the iterator, erase does it for you automatically.

• The const_iterator promises that the pointed value would not be modified through it, which better expresses the intentions, and allows the compiler to optimize code more aggressively.

• head is a misnomer. Call it sentinel, which it actually is.

• I am not sure that the circular list with a sentinel node is a good design. It doesn't buy you anything; memory wise it is worse than standard head and tail pointers; it somewhat complicates the code; it imposes a requirement on T to be constructible from 0.

Answer 3

I see a number of things that may help you improve your code.

Don't shadow template types

The code includes these lines:

namespace Util
{
    template<typename T>
    class Node
    {
    public:
        template<typename T> friend class Iterator;
        template<typename T> friend class List;

There are a few problems here, but one is that the inner declarations shadow the outer one.

Another problem is that the way this code is sructured, the Node class needs to refer to the List and Iterator classes. However, those classes are not defined within the Node.h file and so they need forward declarations. To address both these issues, one could place a forward declaration within the Util namespace:

template<typename T>
class List;

Then within the class, the friend line would look like this:

friend class List<T>;

Better, however, would be the next suggestion:

Reconsider the packaging

I would think there is very little use of Node outside the context of a List. For that reason, I'd suggest that it should be a private class within List and therefore, the Node.h file would go away. Similar logic applies to Iterator.h

Document or eliminate template limitations

If we try to build a List<std::string> it will fail with the current code because of this line:

List<T>::List() : head(new Node<T>(0)), list_size(0)

The problem is that that passing a 0 to the Node constructor only works if the templated type T can be constructed that way and std::string cannot. If instead, a default Node constructor were written, we could write this:

List<T>::List() : head(new Node<T>), list_size(0) {}

There is more, but it's all I have time for at the moment.