Optimising a LinkedList data structure - Part 1

Question

I have implemented a linked list. I feel I overdid it with pointers, used old standards and C++11, and I ended with too many lines of code. I will make my quotations into two parts: one for the Node and iterator struct and the other for rest of the class.

For node and iterator, how can I optimize for C++11? Can you review it?

#include <vector>
#include <cassert>
template <typename T_>
class LinkedList
{
private:  
    struct Node
    {
        T_ data;
        Node* prev;
        Node* next;
        /*Node(T_ D, Node* p = nullptr, Node* n = nullptr) : data(d), prev(p), next(n) {}*/

        Node( const T_ & d = Object{ }, Node * p = nullptr, Node * n = nullptr )
          : data(d), prev(p), next(n) { }

        Node( T_ && d, Node * p = nullptr, Node * n = nullptr )
          : data( std::move(d)), prev(p), next(n) { }


        Node( Node && n ) {        // Rvalue move ctor
            data = std::move(n.data);
            prev = std::move(n.prev);
            next = std::move(n.next);
        }
        Node& operator = ( Node && n ) { // Rvalue = operator
            data = std::move(n.data);
            prev = std::move(n.prev);
            next = std::move(n.next);
            return *this;
        }
        void swap(Node& rhs) throw ()
        {
            std::swap(prev, rhs.prev); std::swap(next, rhs.next);
        }
    };

public:
    struct LinkedListIterator : public std::iterator<std::forward_iterator_tag, T_, int>
    {
        Node*  _pNode;

        LinkedListIterator(Node* p = nullptr) : _pNode(p) {}


        Node* getNode() { return _pNode; }

        T_ operator * () { return _pNode->data; }
        LinkedListIterator & operator ++ () { _pNode = _pNode->next; return *this; } // pre
        LinkedListIterator operator ++ (int) { LinkedListIterator retval = *this; ++*this; return retval; } // post
        bool operator < ( LinkedListIterator const& rhs ) const { return _pNode < rhs._pNode; }
        bool operator != ( LinkedListIterator const& rhs ) const { return _pNode != rhs._pNode; }
        bool operator == ( LinkedListIterator const& rhs ) const { return _pNode == rhs._pNode; }
    };

Answer 1

There are several small things I can see in class Node:

• You have a move constructor, but no copy constructor.
• You have a move assignment operator, but no copy assignment operator.
• Since you use C++11, you should replace the exception specification throw () (now deprecated) by noexcept.
• Your move assignment operator is not protected against self-assignment. You should add the condition if (&n != this) { ... }.
• Also, if possible, your move constructor and operator= should be noexcept too.

• Generally speaking, with move assignment operator, you don't want to move pointers, you only want to swap them since - I believe - your nodes own the pointed values (more information here).

  Node& operator=(Node&& n) noexcept {
      if (&n != this) {
          std::swap(data, n.data);
          std::swap(prev, n.prev);
          std::swap(next, n.next);
      }
      return *this;
  }
  

Answer 2

For the move stuff you want to use swap when you get down to the level of pointers.

This is because when you move an object the src of the move should be left in a valid but indeterminate state. But you should leave it in a state so that when it is destroyed it will not affect other code.

So this looks OK.

    Node( Node && n )
        // Note there is an implicit constructor of `data` here.
        // So you construct `data` then move the content into it later.
    {
        data = std::move(n.data);
        prev = std::move(n.prev);
        next = std::move(n.next);
    }

But now think of the situation where somebody (a clumsey maintainer a few years from now) adds a destructor to Node that does stuff. The source object n still has its original value of pointer and may affect the list of nodes. What you really want to do is move the content from n but also put n into a state that it can never be harmful to the surrounding code. setting the current objects members to NULL and swapping them achieves this:

    Node( Node && n )
       : data(std::move(n.data))    // move data to dst.
       , prev(NULL)                 // Set up pointers for swap
       , next(NULL)
    {        // Rvalue move ctor
        std::swap(prev, n.prev);    // swaping values should be no-throw.
        std::swap(next, n.next);
    }
    // Now 'n' is completely disconnected.
    // It can not harm the chain no matter what you do.

The next one is more subtle.
You should only use the move of a templated class T if you can guarantee that T has a nothrow move semantics.

    Node& operator = ( Node && n ) { // Rvalue = operator
        data = std::move(n.data);

What happens if half way through this move you throw an exception? Then you leave the source object n in some intermediate state.

If you look at std::vector if the data type used does not have a nothrow move semantics then it will use copy semantics to guarantee that's its operations have the strong exception guarantee. You should strive to have the same semantics in your class.

There is some template magic to do this test but I don;t have my notes with me.

Are you sure you only want a forward iterator?

struct LinkedListIterator : public std::iterator<std::forward_iterator_tag, T_, int>
                                                      ^^^^^^^^^^^^^^^^^^^^

You have a doubly linked list. You can easily support Bi-directional iterator.