Linked list with iterators

Question

This is my second linked list implementation for review. I rewritten pretty much all of this and have added iterators, sentinels and The Rule of Five.

Please let me know what's wrong with it; I am still not confident in many areas.

#include <stdlib.h>
#include <memory>
#pragma once
template <typename T>
class LinkedList;
template <typename TNode>
class LinkedListIterator
{
 friend class LinkedList<typename TNode::value_type>;
 TNode* p;
public:
 LinkedListIterator(TNode* p) : p(p) {}
 LinkedListIterator(const LinkedListIterator& other) : p(other.p) {}
 LinkedListIterator& operator=(LinkedListIterator other) { std::swap(p, other.p); return *this; }
 void operator++() { p = p->next; }
 void operator++(int) { p = p->next; }
 bool operator==(const LinkedListIterator& other) { return p == other.p; }
 bool operator!=(const LinkedListIterator& other) { return p != other.p; }
 const int& operator*() const { return p->data; }
 LinkedListIterator<TNode> operator+(int i)
 {
 LinkedListIterator<TNode> iter = *this;
 while (i-- > 0 && iter.p)
 {
 ++iter;
 }
 return iter;
 }
};
template <typename T>
class Node
{
 friend class LinkedList<T>;
 friend class LinkedListIterator<Node<T>>;
 friend class LinkedListIterator<const Node<T>>;
 Node() : next(nullptr) {}
 Node(const T &data) : data(data), next(nullptr) {}
 Node<T> *next;
 T data;
public:
 typedef T value_type;
};
template <typename T>
class LinkedList
{
 typedef Node<T> node;
 std::size_t size;
 std::unique_ptr<node> head;
 std::unique_ptr<node> tail;
 void init()
 {
 size = 0;
 head.reset(new node);
 tail.reset(new node);
 head->next = tail.get();
 }
public:
 typedef LinkedListIterator<node> iterator;
 typedef LinkedListIterator<const node> const_iterator;
 LinkedList() { init(); }
 LinkedList(const LinkedList& other)
 {
 init();
 const_iterator i = other.begin();
 while (i != other.end())
 {
 add(*i);
 i++;
 }
 head.reset(other.head.get());
 tail.reset(other.tail.get());
 }
 LinkedList(LinkedList&& other)
 {
 init();
 size = other.size;
 head = other.head;
 tail = other.tail;
 other.first = nullptr;
 other.size = 0;
 }
 LinkedList& operator=(LinkedList other)
 {
 swap(*this, other);
 return *this;
 }
 LinkedList& operator=(LinkedList&& other)
 {
 assert(this != &other); 
 while (head->next != tail)
 remove(begin());
 head = other.head;
 tail = other.tail;
 size = other.size;
 first = other.first;
 other.size = 0;
 other.first = nullptr;
 return *this;
 }
 virtual ~LinkedList()
 {
 while (head->next != tail.get())
 remove(begin());
 }
 friend void swap(LinkedList& first, LinkedList& second)
 {
 std::swap(first.size, second.size);
 std::swap(first.head, second.head);
 std::swap(first.tail, second.tail);
 }
 void add(const T &value)
 {
 node *first = new node(value);
 first->next = head->next;
 head->next = first;
 size++;
 }
 void remove(iterator& removeIter)
 {
 node *last = head.get();
 iterator i = begin();
 while (i != removeIter)
 {
 last = i.p;
 ++i;
 }
 if (i != end())
 {
 last->next = i.p->next;
 size--;
 delete i.p;
 }
 }
 const int getSize() 
 { 
 return size;
 }
 iterator begin() 
 {
 return iterator(head->next);
 }
 const_iterator begin() const
 {
 return const_iterator(head->next);
 }
 iterator end()
 {
 return iterator(tail.get());
 }
 const_iterator end() const
 {
 return const_iterator(tail.get());
 }
};

• MiJyn: I would recommend using (e.g.) this->size instead of just size
• Yuushi: @MiJyn I disagree. Unnecessary prefacing of member variables with this-> is not generally seen as good style.
• MiJyn: @Yuushi seriously? I personally find that it makes code harder to read

Answer 1

In all, this is pretty well structured code and I had no problem reading and understanding it. Whenever another programmer can read and understand your code, it's a good sign that you're on the right track. So what's left is mostly small points that might improve your code. Here's what I noticed in no particular order.

Use the appropriate #includes

This code uses std::swap which is actually defined in <algorithm> up to C++11, but <utility> in more recent versions of the standard. You've included <stdlib.h> but in a C++ program that should actually be <cstdlib> which puts the various declarations into the std:: namespace rather than in the global namespace.

Use the right forms of const

The LinkedList class contains a getSize() function. Right now that's declared as

const int getSize() // const will be ignored for this return type

but I think what you really meant was this:

int getSize() const // this call does not alter the underlying object

Don't use variables that are not in scope

The two move operators of the LinkedList class both refer to a member data pointer named first but no such variable is actually declared. The three lines in those two functions that refer to first should simply be deleted.

Think about temporary object usage

The LinkedList class includes a number of member functions in which remove(begin()) is called. However, a close look shows that begin() returns a temporary of type iterator. However, the remove() function takes a non-const reference to an iterator and so we have a problem. One solution is to change remove to use move semantics.

Another problem is easily shown when using this common C++11 idiom to print all of the data members of the linked list:

for (const auto &val : mylist)
 std::cout << val << '\n';

The intent here is to print the values of all of the linked list values without modifying them (hence const) and without copying them (hence &). Unfortunately this won't work with the current version of the code. The problem is once again the use of temporary values. In particular, this effectively calls this operator:

const int& operator*() const { return p->data; }

But p->data isn't necessarily an int so the way to fix this is:

typename TNode::value_type& operator*() const { return p->data; }

Write member initializers in declaration order

The Node class has this constructor

Node(const T &data) : data(data), next(nullptr) {}

That looks fine, but in fact, next will be initialized before data because members are always initialized in declaration order and next is declared before data in this class. To avoid misleading another programmer, you should swap the order of those such that it says instead:

Node(const T &data) : next(nullptr), data(data) {}

This way the initialization actually proceeds from left to right as one might expect at first glance.

Iterator increment operators should return a reference

The code has two increment operators, a preincrement and a postincrement:

void operator++() { p = p->next; }
void operator++(int) { p = p->next; }

However, consider the following use:

for (auto it = ll.begin(); it != ll.end(); )
 std::cout << *it++ << '\n';

This will fail because it++ returns void instead of a reference to a LinkedListIterator. The preincrement is easy to fix:

LinkedListIterator& operator++() { p = p->next; return *this; }

The postincrement cannot be the same thing, though, because it is required to return the value before the increment. In other words, if int i = 5; we would expect std::cout << ++i << '\n'; to print "6" but std::cout << i++ << '\n'; should print "5". So to fix the postincrement we do this:

LinkedListIterator operator++(int) { LinkedListIterator it(*this); p = p->next; return it; }

Note that this returns an actual LinkedListIterator object and not an object reference as with the preincrement operator.

Consider making the iterators more general purpose

As it stands, an attempt to sort an instance of this LinkedList using std::sort will fail:

std::sort(ll.begin(), ll.end());

The problem is that std::sort expects to be able to check iterator traits (such as random_access_iterator_tag) to tell the Standard Template Library (STL) which iterators can support which algorithms.

Use cbegin and cend

The STL uses cbegin and cend as names for the constant versions of the iterator members. This is convenient because it allows usage such as this:

for (auto it = ll.cbegin(); it != ll.cend(); ++it)
 // do something with each member

This code can easily be modified to conform to this by simply renaming the two functions.

Fix your copy constructors

This code will cause a seg fault:

#include <iostream>
int main()
{
 LinkedList<std::string> ll;
 ll.add("one");
 LinkedList<std::string> l2 = ll;
 l2.add("two");
 std::cout << "The copy\n";
 for (auto it = l2.begin(); it != l2.end(); ++it)
 std::cout << *it << '\n';
 std::cout << "The original\n";
 for (auto it = ll.begin(); it != ll.end(); ++it)
 std::cout << *it << '\n';
}

The problem is in the copy constructor:

LinkedList(const LinkedList& other)
{
 init(); // head is created and points to tail
 const_iterator i = other.begin();
 while (i != other.end())
 {
 add(*i); // head now points to last added node
 i++;
 }
 head.reset(other.head.get()); // head now points to other's first node!
 tail.reset(other.tail.get());
}

Clearly those last two lines are not helpful, and we can also clean up the rest:

LinkedList(const LinkedList& other)
{
 init(); 
 for (auto i = other.cbegin(); i != other.cend(); ++i)
 add(*i); 
}

Unfortunately, the move constructor has a similar problem, but I'll leave it to you to fix. Generally speaking, you may want to instrument your code and make sure that you have exercised all member functions, ideally with a few different kinds of data (I tend to use std::complex and std::string as convenient and complete classes for testing container templates).

• ruds: I'm confused by your advice about operator*() const, which you suggest should return a copy of the value; you say that return p->data; creates a temporary of some sort. It would be unusual to return a copy here, and undesirable whenever T is large. The lifetime of p->data shouldn't be an issue; it is normal for iterators to be invalidated (i.e. it is undefined behavior to use them) when e.g. the collection they iterate over is destroyed.
• Edward: @ruds: rereading what I wrote there, I'm inclined to agree with you. There are other problems with the code but this isn't one of them. I have amended my answer. Thanks.

Answer 2

• operator!= must be defined as a negation of operator==.
• A (non-random-access) forward iterator shall not define an operator+. std::advance does the job.
• I don't think that operator++ can be void.

Otherwise looks very compliant.

PS: did you try it against STL's find, copy and friends and family?

• Jerry Coffin: [citation needed] for the requirement that operator != be implemented as a negation of operator==.
• vnp: I can't quote a video here, sorry. Alex Stepanov goes deep on the topic in his lectures at youtube.com/user/A9Videos/videos
• Beta: I find it hard to believe that a good reason could not be stated briefly enough to fit here, but could you at least tell us which video?
• vnp: @Beta Briefly: a "not equal" relation is a negation of an "equal" relation, by definition. An attempt to define it in any other way is wrong. A very interesting discussion is in Programming Conversations 11 (part 2 specifically). However I highly recommend all of them.
• TemplateRex: only the semantics of a!=b should be !(a==b), not the actual implementation. You could equally define a==b as !(a!=b)

Answer 3

Other answers got most things, I am just adding what they missed.

---

1) Avoid having same names of member variables and method arguments

LinkedListIterator(TNode* p) : p(p) {} --- Avoid having same names of member variables and method arguments, since if you need to use it in the constructor, you may be surprised of what gets used.

For example :

LinkedListIterator(TNode* p) : p(p) {
 ++ p; // ops method argument modified
}

2) Avoid having init functions

The constructors are for the class initialization, therefore try to avoid having such functions. As other answers showed, you even made it wrong.

If you need to initialize common things in several constructors, you can use this way of initializing common member variables.

3) Try to avoid using the friend keyword

The fact that you used the friend keyword in so many places, indicates that the coupling of your classes is high, meaning you didn't do your design properly.

• Edward: Good point on the init function, but the link you provide is not a good one. In fact, the problem with the existing init is that it causes the constructor to invoke head.reset() and tail.reset() before head or tail are constructed.

Answer 4

Provide the other iterator-returning methods.

Right now, the code provides const and mutable versions of begin() and end(). To act like the standard containers, we should also provide the rest (boilerplate):

using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
const_iterator cbegin() const { return begin(); }
const_iterator cend() const { return end(); }
reverse_iterator rbegin() { return std::make_reverse_iterator(begin()); }
reverse_iterator rend() { return std::make_reverse_iterator(end()); }
const_reverse_iterator rbegin() const { return std::make_reverse_iterator(begin()); }
const_reverse_iterator rend() const { return std::make_reverse_iterator(end()); }
const_reverse_iterator crbegin() const { return rbegin(); }
const_reverse_iterator crend() const { return rend(); }

Missing iterator method

It's easily overlooked, but required by InputIterator concept:

const auto* operator->() const { return &p->data; }
auto* operator->() { return &p->data; }

(I note in passing that operator*() has been declared with the wrong return type - that needs to be fixed).