Suggestions to My Generic Doubly-Linked List

Question

Here's my doubly-linked list implementation. I'd like to hear what the community has to say, and what feedback I can get to further improve it.

#pragma once
#include <cstdlib>
#include <ostream>
#include <iostream>
#include <cassert>
#define CHECK assert(Invariant());
template <class T>
class List
{
 class Node; // forward decleration
 class Link
 {
 friend class List<T>;
 Link* _next;
 Link* _prev;
 Link() : _next(this), _prev(this) {}
 public:
 void InsertBefore(Node* toInsert)
 {
 toInsert->_next = _next;
 toInsert->_prev = this;
 _next->_prev = toInsert;
 _next = toInsert;
 }
 void InsertAfter(Node* toInsert)
 {
 toInsert->_next = this;
 toInsert->_prev = _prev;
 _prev->_next = toInsert;
 _prev = toInsert;
 }
 Link* Remove()
 {
 _prev->_next = _next;
 _next->_prev = _prev;
 return *this;
 }
 void PointTowardsEachOther(Link* second)
 {
 this->_next = second;
 second->_prev = this;
 }
 
 void splice_after(Link* first, Link* last){}
 void splice_before(Link* first, Link* last){}
 };
 class Node : public Link
 {
 friend class List;
 T _data;
 public:
 Node(const T& data) : _data(data) {};
 };
 template<class X> 
 class ListIter
 {
 friend class List<T>;
 Node* _ptr;
 public:
 using iterator_category = std::forward_iterator_tag;
 using value_type = T;
 using difference_type = std::ptrdiff_t;
 using reference = X&;
 using pointer = X*;
 ListIter(const Link* p = nullptr) : _ptr(static_cast<Node*>(const_cast<Link*>(p))) {}
 ListIter(const ListIter&) = default;
 
 ListIter& operator= (const ListIter & other) = default;
 
 
 X& operator*()
 {
 return _ptr->_data;
 }
 X* operator->()
 {
 return &_ptr->_data;
 }
 ListIter& operator++()
 {
 _ptr = static_cast<Node*>(_ptr->_next);
 return *this;
 }
 ListIter& operator--()
 {
 _ptr = static_cast<Node*>(_ptr->_prev);
 return *this;
 }
 ListIter operator++(int)
 {
 auto temp(*this);
 operator++();
 return temp;
 }
 ListIter operator--(int)
 {
 auto temp(*this);
 operator--();
 return temp;
 }
 friend bool operator == (const ListIter& lhs, const ListIter& rhs) = default;
 friend bool operator != (const ListIter& lhs, const ListIter& rhs) = default;
 };
 Link _head;
public:
 using iterator = ListIter<T>;
 using const_iterator = ListIter<const T>;
 ~List()
 {
 while (_head._next != &_head)
 {
 pop_front();
 }
 CHECK
 }
 List()
 {
 _head._next = &_head;
 _head._prev = &_head;
 CHECK
 }
 List(const List& other) : List()
 {
 if (other.Count() > 0)
 {
 Link* ptr = other._head._next;
 while (ptr != &other._head)
 {
 push_back(static_cast<Node*>(ptr)->_data);
 ptr = ptr->_next;
 }
 }
 CHECK
 }
 List(const char* other) : List()
 {
 const char* ptr = other;
 while (*ptr != '0円')
 {
 push_back(*ptr);
 ++ptr;
 }
 CHECK
 }
 T& front()
 {
 return static_cast<Node*>(_head._next)->_data;
 }
 const T& front() const
 {
 return static_cast<Node*>(_head._next)->_data;
 }
 T& back()
 {
 return static_cast<Node*>(_head._prev)->_data;
 }
 const T& back() const
 {
 return static_cast<Node*>(_head._prev)->_data;
 }
 bool empty() const noexcept
 {
 return begin() == end();
 }
 size_t size() const noexcept 
 {
 return std::distance(cbegin(), cend());
 }
 iterator insert(iterator pos, const T& value)
 {
 pos._ptr->InsertAfter(new Node(value));
 return pos._ptr->_prev;
 }
 
 iterator erase(const iterator& pos) 
 {
 iterator temp = pos;
 ++temp;
 pos._ptr->_prev->_next = pos._ptr->_next;
 pos._ptr->_next->_prev = pos._ptr->_prev;
 delete pos._ptr;
 CHECK
 return temp;
 }
 void push_back(const T& toInsert)
 {
 Node* node = new Node(toInsert);
 _head.InsertAfter(node);
 }
 void push_front(const T& toInsert)
 {
 Node* node = new Node(toInsert);
 _head.InsertBefore(node);
 }
 void pop_back()
 {
 delete _head.DeleteLast();
 CHECK
 }
 void pop_front()
 {
 delete _head.DeleteFirst();
 CHECK
 }
 List& operator=(const List& other)
 {
 List newList(other);
 swap(newList);
 return *this;
 }
 void splice(const_iterator pos, List& other, const_iterator first, const_iterator last)
 {
 if (first == last)
 {
 return;
 }
 
 Link* beforePos = pos._ptr->_prev;
 Link* beforeFirst = first._ptr->_prev;
 Link* beforeLast = last._ptr->_prev;
 beforePos->PointTowardsEachOther(first._ptr);
 beforeFirst->PointTowardsEachOther(last._ptr);
 beforeLast->PointTowardsEachOther(pos._ptr);
 CHECK
 }
 void swap(List<T>& rhs)
 {
 bool thisEmpty = empty();
 bool rhsEmpty = rhs.empty();
 if (thisEmpty && rhsEmpty)
 {
 return;
 }
 else if (thisEmpty)
 {
 _head._next = rhs._head._next;
 _head._next->_prev = &_head;
 _head._prev = rhs._head._prev;
 _head._prev->_next = &_head;
 rhs._head._next = &rhs._head;
 rhs._head._prev = &rhs._head;
 }
 else if (rhsEmpty)
 {
 rhs._head._next = _head._next;
 rhs._head._next->_prev = &rhs._head;
 rhs._head._prev = _head._prev;
 rhs._head._prev->_next = &rhs._head;
 _head._next = &_head;
 _head._prev = &_head;
 }
 else
 {
 Link* temp1 = _head._next;
 Link* temp2 = _head._prev;
 _head._next = rhs._head._next;
 _head._next->_prev = &_head;
 _head._prev = rhs._head._prev;
 _head._prev->_next = &_head;
 rhs._head._next = temp1;
 rhs._head._next->_prev = &rhs._head;
 rhs._head._prev = temp2;
 rhs._head._prev->_next = &rhs._head;
 }
 CHECK
 }
 friend void swap(List<T>& lhs, List<T>& rhs)
 {
 lhs.swap(rhs);
 }
 friend auto operator<=> (const List& lhs, const List& rhs)
 {
 auto lIt = lhs.begin();
 auto rIt = rhs.begin();
 for (; lIt != lhs.end() && rIt != rhs.end(); ++lIt, ++rIt)
 if (*lIt < *rIt)
 return std::strong_ordering::less;
 else if (*lIt > *rIt)
 return std::strong_ordering::greater;
 if (lIt == lhs.end())
 if (rIt == rhs.end())
 return std::strong_ordering::equivalent;
 else
 return std::strong_ordering::less;
 else
 return std::strong_ordering::greater;
 }
 friend bool operator==(const List& lhs, const List& rhs)
 {
 return (lhs <=> rhs) == 0;
 }
 friend bool operator!=(const List& lhs, const List& rhs)
 {
 return (lhs <=> rhs) != 0;
 }
 friend std::ostream& operator<<(std::ostream& cout, const List& other)
 {
 for (auto it = other.begin(); it != other.end(); ++it)
 {
 cout << *it << " ";
 }
 cout << std::endl;
 return cout;
 }
 std::ostream& Print(std::ostream& cout)
 {
 for (auto ptr = _head._next; ptr != &_head; ptr = ptr->_next)
 {
 cout << static_cast<Node*>(ptr)->_data << " ";
 }
 cout << std::endl;
 return cout;
 }
 size_t Count() const
 {
 size_t count = 0;
 for (auto ptr = _head._next; ptr != &_head; ptr = ptr->_next)
 {
 count++;
 }
 return count;
 }
 bool Invariant() const {
 size_t i = 0;
 for (auto ptr = _head._next; ptr != &_head; ptr = ptr->_next)
 {
 if (++i == std::numeric_limits<size_t>::max())
 return false;
 if (ptr->_next->_prev != ptr)
 return false;
 }
 return true;
 }
 iterator begin() { return iterator(_head._next); }
 const_iterator begin() const { return const_iterator(_head._next); }
 const_iterator cbegin() const { return const_iterator(_head._next); }
 iterator end() { return iterator(&_head); }
 const_iterator end() const { return const_iterator(&_head); }
 const_iterator cend() const { return const_iterator(&_head); }
};

Answer 1

We're missing an include of <limits>. Sorting the includes can help spot this more quickly. We don't seem to be using anything from <cstdlib> or <iostream>.

We should #undef CHECK before the end of the file. It would be better defined without the semicolon, so it can be written as an expression CHECK; (that can help tools get the indentation right).

Better yet, just drop the macro, and simply write assert(Invariant()); in full - that makes the code clearer to read. I'm wondering if it's really worth the hit of this test in debug builds - it might be better not to validate the invariant all the time, and instead have all the unit tests to the checking. That helps isolate the causes of breakage.

The only comment in this code is one that's unnecessary (it just repeats what the code says, and it's not even spelt correctly).

Why do splice_after() and splice_before() do nothing? Are they present just to mislead users?

I'm not sure there's much to be gained from separating the concerns of Link and Node, especially given that they are both private classes - if we combine them into a single class, we eliminate a lot of static_cast<Node*>(). The downside is that it's then hard to create the dummy-head node for a T that's not default-constructible, so we might need to put up with the casts (though shouldn't they really be reinterpret_cast()?).

List really should have move constructor and assignment operator for efficient copy of a List&&. It would also be nice to have an initialiser-list constructor.

We're missing a conversion from iterator to const_iterator. Fixing that will avoid user surprise and also make our implementation easier.

front() can be simplified - just return *begin(). Similarly back() can return *rbegin().

The size() function doesn't conform to complexity requirements of standard containers (it should execute in constant time). It's worth maintaining a count of elements so that we can use generic algorithms safely.

insert() and erase usually both take a const_iterator - it's normal to find the position without modifying values; we only need the List to be modifiable (this is one reason we want a conversion from iterator).

pop_back() and pop_front() fail to compile at all, due to missing DeleteLast() and DeleteFirst() member functions in Link.

operator= should take its argument by value. Then we don't need to make a copy within its definition.

swap() looks over-complicated. Why not just swap the head members directly? I see we need to fix up the pointers back to head, but if we do that first, we don't need different code for empty and non-empty lists:

// untested
void swap(List<T>& other) noexcept
{
 _head._next->_prev = _head._prev->_next
 = &other._head;
 other._head._next->_prev = other._head._prev->_next
 = &_head;
 std::swap(_head, other._head);
}

operator<=>() could be implemented with a single call to std::lexicographical_compare(). It only really makes sense when T is comparable, so consider applying a constraint to disable it otherwise.

operator<<() could use a range-based for; it certainly shouldn't be flushing the stream. If a newline is required (I'd argue it isn't) write '\n' rather than std::endl.

What's the Print() function for? It seems to be a duplicate of operator<<().

Similarly, Count() appears to be a duplicate of size().

Invariant() has a very expensive way of detecting a loop in the list. Consider implementing a tortoise and hare algorithm instead.

The review would be easier if you had included your unit tests along with the class code - I encourage you to do that for future reviews.

Answer 2

Review

Macros are not a bad idea:

#define CHECK assert(Invariant()); 

Don't add the ; at then end of the macro. You are going to confuse some tools. Also at least make it look like a function call:

#define CHECK() assert(Invariant())

If you follow most guidelines on this it should also be written as a do loop.

#define CHECK() do { assert(Invariant()) } while(false)

This covers some corner cases in usage.

BUT I personally would simply get rid of the macros. You can define an inline function that achieves the same thing with no dangers.

inline void Check(obj) {assert(obj.Invariant());}

OR

You can simply write the line in the code:

 assert(Invariant()); // On Debug builds validate the state.

---

Since Node and Link are private members I don't see the need to make them class, I would rather make it simpler and define them as struct.

Looking at Link:

I don't you need several of these functions.

• void InsertBefore(Node* toInsert)
  is only used in push_front() and could be simply written by using a simpler constructor for Node.

   void push_front(const T& toInsert)
   {
   new Node(&head, &head->next, toInsert)
   }
  

• void InsertAfter(Node* toInsert)
  is used in push_back() and insert() could again be done by using the Node constructor.

   void push_back(const T& toInsert)
   {
   new Node(&head->prev, &head, toInsert)
   }
  

• Link* Remove()
  Never used. Remove it.

• void PointTowardsEachOther(Link* second)
  Could probably be better written in place at the point of usage.

• splice_after / splice_before
  Never used. Remove them.

I would simplify the List/Node classes down to:

class List
{
 struct Node;
 struct Link
 {
 List* next;
 List* prev;
 Link(List* prev, List* next);
 };
 struct Node: public Link
 {
 T data;
 Node(List* prev, List* next ,T const& data)
 : Link(prev, next)
 , data(data)
 {}
 Node(List* prev, List* next ,T&& data)
 : Link(prev, next)
 , data(std::move(data))
 {}
 };
};
List::Link::Link(List* prev, List* next)
 : prev(prev)
 , next(next)
{
 prev->next = this;
 next->prev = this;
}
 

---

This means the constructor of List needs to change:

 List()
 head(&head, &head)
 {
 assert(Invariant());
 }

---

An interesting specialization of the constructor.

 List(const char* other) : List()
 {
 const char* ptr = other;
 while (*ptr != '0円')
 {
 push_back(*ptr);
 ++ptr;
 }
 CHECK
 }

Don't think this gains you anything.
I would prefer to see a constructor that takes two iterators. That would be more generic and cover this corner case.

 template<typename I>
 List(I begin, I end);

Then you could use it like:

 char data[] = "This is my string";
 List list(std::begin(data), std::end(data));

---

Don't like that you have exactly the same code twice (i.e the code is not DRY). This leads to issues when you have bugs which you fix in one place rather than all locations. Prefer to define this in one function and then have the other function call the first function.

 T& front()
 {
 return static_cast<Node*>(_head._next)->_data;
 }
 const T& front() const
 {
 return static_cast<Node*>(_head._next)->_data;
 }
 T& back()
 {
 return static_cast<Node*>(_head._prev)->_data;
 }
 const T& back() const
 {
 return static_cast<Node*>(_head._prev)->_data;
 }

---

That's a very expensive way of computing empty.

 bool empty() const noexcept
 {
 return begin() == end();
 }

Why not simplify to:

 bool empty() const noexcept {return head.next == &head;}

---

Very expensive way to compute size(). Even more so than empty() as these are not random-access iterators so you need to actually loop over the iterators to find the end.

 size_t size() const noexcept 
 {
 return std::distance(cbegin(), cend());
 }

In this case I would keep an explicit track of the number of members.

---

This used to be the way to write the copy and swap:

 List& operator=(const List& other)
 {
 List newList(other);
 swap(newList);
 return *this;
 }

It has changed to this:

 List& operator=(List other) noexcept
 {
 swap(other);
 return *this;
 }

The thing to note here: this version works for both copy and move operations.

---

I think you can simplify swap() lot:

 void swap(List<T>& rhs) noexcept
 {
 bool thisEmpty = empty();
 bool rhsEmpty = rhs.empty();
 using std::swap();
 // Lets just swap the head nodes unconditionally.
 swap(head, rhs.head);
 // Now fix for the special case where the list was empty.
 if (thisEmpty) {
 rhs.head.next = rhs.head.prev = &rhs.head;
 }
 if (rhsEmpty) {
 head.next = head.prev = &head;
 } 
 CHECK
 }

---

Seems like these are doubled up:

Why not make the operator<< use the Print() method?

 friend std::ostream& operator<<(std::ostream& cout, const List& other)
 {
 for (auto it = other.begin(); it != other.end(); ++it)
 {
 cout << *it << " ";
 }
 cout << std::endl;
 return cout;
 }

The one change I would make here is to default the stream:

 std::ostream& Print(std::ostream& cout = std::cout)

---

Don't use std::endl. It is never a good idea.

 cout << std::endl;

---

Answer to comment: How would you suggest implementing

void splice_after(Link* first, Link* last)
{}
void splice_before(Link* first, Link* last)
{}

In short I would not implement either of these.

I think a better to design is to look at what is needed at the List interface. If we look at the standard containers. The interface is:

void list::insert(iterator position, const value_type& value);

Here the interface is simply to insert the value "before" the provided iterator.

This is simply defined as:

// Pass data by value.
// This then implements both move and copy semantics in a
// single function (assuming T implements move semantics).
void List::insert(List::iterator position, T value)
{
 // This line will depend on you making List a friend of 
 // ListIter (which it already is) or simply maing ListIter
 // a struct.
 Node* iteratorNode = position._ptr;
 new Node(iteratorNode->prev, iteratorNode, std::move(value));
}

The Node/Link constructor handle correctly inserting the value into the list once we have identified the previous and next objects in the list.

• Toby Speight: Your suggested Node constructor doesn't need to be overloaded on const T& / T&& - just pass by value: Node(List* prev, List* next , T data) : Link{prev, next}, data{std::move(data)} {}
• Loki Astari: @TobySpeight: I thought about that. But what about the situation where the object does not have move semantics. In that case you end up with two copies.
• Alix Blaine: @MartinYork, thx. How would you suggest implementing the void splice_after(Link* first, Link* last){} void splice_before(Link* first, Link* last){}, where the pos is this ???
• Loki Astari: @AlixBlaine: Added a section to the end of my answer.
• Alix Blaine: @MartinYork, but, if you need to have them, how would you go about writing one of them or both? I been curiously trying to figure this part out for weeks, and still cannot wrap my head around this. I managed to figure out the splice method at least. But, the other too, seem complicated.

Answer 3

What that Link class should be good for? Node is the only child class of Link, so all the functionality from Link should be put directly into Node. Since Node is an internal private class inside List, no need to define List as a friend. The same thing for the ListIter class no need to define List as a friend. The Head is normally a pointer to the first element of the list, making it a Link object that looks a bit strange. Also since it ́s a Doubly-Linked List, there should be a pointer to the tail of the list, so you can iterate in both directions.

• Toby Speight: There's arguably a benefit to separating concerns, but I think I agree with you here.
• Deduplicator: @TobySpeight Node might be the only derived class, but there is also a Link in List.
• Loki Astari: I think you do need to split Link/Node. The design uses a Sentinel to simplify the design (this means you don't need to add a bunch of checks for nullptr all around the code so a great design). BUT the sentinel node can not have data itself (if it did you could not use it for types T that are not default constructable, also it would be wasteful for types T that are expensive to construct as you have a non used value in the Sentinel.
• Toby Speight: @Martin, exactly the conclusion I was arriving at!