Example of linked lists types.

Single linked

Single linked basic

A single linked basic list is linear, with a minimalistic header and iterator. The end iterator is just a nullptr value.

Single linked basic

It does not offer offer constant time access to the back and push_back.

This is a good candidate for a std::forward_list implementation. Also it’s a list with minimalistic memory usage (for a linked list).

Single linked circular

A single linked circular list has a minimalistic header (pointing to the tail), a (relatively) complex iterator (to differentiate between a past the tail and a pointer to the head), and two step head access.

Single linked circular

It allows constant time access to the back and push_back.

The iterator needs to know the tail so that iterating past the tail results in reaching the end as opposed to starting again from the beginning. There are several options with regards on how the iterator can get the value of the tail. It can contain the pointer to the tail directly, as shown above, or it can contain a pointer to the list header and dereference it to get the tail (indirectly). These choices result in different behaviours when the list has additional nodes added at the end while enumerating, and also in the number of operations required to increment an iterator.

Single linked first-last

A single linked linear list with pointers in the header to the first and last also allows constant time access to the back and push_back, by making different choices: it has a simple iterator, but header is not minimalistic.

Single linked first-last

Single linked summary

Option vs. List type Single linked basic Single linked circular Single linked first-last
Single or Double linked Single Single Single
Linear or Circular Linear Circular Linear
Minimalistic header Yes Yes No
Links to local parts No No No
Dummy node No No No
Minimalistic iterator Yes No Yes
Permanent end Yes Yes Yes
Iterator type Forward Forward Forward
front, push_front, pop_front, insertion/erasure after Yes Yes Yes
back, push_back No Yes Yes
pop_back No No No
insert/erase at/before No No No

Options in bold are not the best compared with other list types.

All single lists lack some features compared with some double linked lists.

With regards to constant time back and push_back the options for single lists are:

  • do not provide
  • provide, but trade-off for either a non-minimalistic iterator or a non-minimalistic header

Double linked

Double linked linear

A double linked linear list with minimalist header and iterator.

Double linked linear

This is useful for intrusive lists where you retrieve an iterator based on a reference to the value, and then can remove the node from the list, all while keeping the rest as simple as possible.

Double linked circular

A circular double linked list without a dummy node has a minimalist header, but a (relatively) complex iterator and no fixed end iterator.

Double linked circular

Like the single linked circular, there are two option on how the iterator gets the value of the tail: directly, as above, or indirectly, through the header.

Double linked with allocated dummy node

A circular double linked list with an allocated dummy node has a minimalistic header and iterator.

Double linked dummy node

There are however two options with regards to the presence of the dummy node, neither of which is particularly palatable.

Double linked dummy node options

  • One option (1) is to always ensure the dummy node is present. This means that it provides a fixed end iterator, but it leads to a throwing default destructor and move constructor. In particular the std::list in Visual Studio 2017 uses this option, which can be confirmed:
1
2
3
4
5
6
7
8
9
10
11
#include <list>
#include <type_traits>

static_assert(std::is_nothrow_default_constructible_v<std::list<int>>,
  "Default constructor may throw");
static_assert(std::is_nothrow_move_constructible_v<std::list<int>>,
  "Move constructor may throw");

// The above fails to compile for Option 1 with messages similar to:
// source.cpp: error C2338: Default constructor may throw
// source.cpp: error C2338: Move constructor may throw
  • Another option (2) is to ensure the default destructor and move constructor do not throw, but lose a fixed end iterator and a (relatively) more complex logic to deal with a potentially missing dummy node.

I find option (1) particularly troubling and not a choice to take with ease: throwing default and move constructors are highly irregular.

Double linked with dummy node in header

A circular double linked list with the dummy node in the header, does not has a minimalistic header, but has a minimalistic iterator and a fixed end iterator.

Double linked dummy node in header

The downside is that during move operation the pointers from the head and tail pointing back to the header need to be adjusted.

Double linked summary

Option vs. List type Double linked linear Double linked circular Double linked allocated dummy node Double linked dummy node in header
Single or Double linked Double Double Double Double
Linear or Circular Linear Circular Circular Circular
Minimalistic header Yes Yes Yes No
Links to local parts No No No Yes
Dummy node No No Yes in header
Minimalistic iterator Yes No Yes Yes
Permanent end Yes No / Yes No / Yes Yes
Iterator type Forward Bidirectional Bidirectional Bidirectional
front, push_front, pop_front, insertion/erasure after Yes Yes Yes Yes
back, push_back No Yes Yes Yes
pop_back No Yes Yes Yes
insert/erase at/before Yes Yes Yes Yes
Throwing default/move No No No / Yes No

Options in bold are not the best compared with other list types.

Double linked nodes are larger by one pointer size to the single linked ones, but they provide insert and erase before iterator.

Double linked with allocated dummy node need to make choose between:

  • No permanent end
  • Or throwing default and move constructors

Double linked with dummy node in header is a good choice overall. Note that although it uses additional space for the dummy node, we already counted this as a downside for the non-minimalistic header.

Other variations

Variations of the above are possible for:

  • cached list size in the header
  • allocator/ownership
  • intrusive vs. non-intrusive

References

Alexander A. Stepanov and Paul McJones:
Elements of Programming