Linked-list in C++ using references instead of pointers

Take a look at this example by sbi, it seems to work: https://stackoverflow.com/a/3003607/1758762

// Beware, un-compiled code ahead!
template< typename T >
struct node;

template< typename T >
struct links {
  node<T>& prev;
  node<T>& next;
  link(node<T>* prv, node<T>* nxt); // omitted
};

template< typename T >
struct node {
  T data;
  links<T> linked_nodes;
  node(const T& d, node* prv, node* nxt); // omitted
};

// technically, this causes UB...
template< typename T >
void my_list<T>::link_nodes(node<T>* prev, node<T>* next)
{
  node<T>* prev_prev = prev.linked_nodes.prev;
  node<T>* next_next = next.linked_nodes.next;
  prev.linked_nodes.~links<T>();
  new (prev.linked_nodes) links<T>(prev_prev, next);
  next.linked_nodes.~links<T>();
  new (next.linked_nodes) links<T>(next, next_next);
}

template< typename T >
void my_list<T>::insert(node<T>* at, const T& data)
{
  node<T>* prev = at;
  node<T>* next = at.linked_nodes.next;
  node<T>* new_node = new node<T>(data, prev, next);

  link_nodes(prev, new_node);
  link_nodes(new_node, next);
}

This is typical of a cons-list in functional languages:

data List a = Empty | Node a (List a)

The trick is though, List a is a full type and can refer either to Empty OR another node (which is why it can terminate).

In order to achieve this in C++, you could take advantage of either a union (but it's not that well supported) or of polymorphism.

template <typename T>
struct ListBase {
    enum class Kind { Empty, Node };
    explicit ListBase(Kind k): _kind(k) {}

    Kind _kind;
};

And then:

template <typename T>
struct EmptyList: ListBase<T> {
    EmptyList(): ListBase<T>(Kind::Empty) {}
};

template <typename T>
struct ListNode: ListBase<T> {
    ListNode(T const& t, ListBase<T>& next):
        ListBase<T>(Kind::Node), _value(t), _next(next) {}

    T _value;
    ListBase<T>& _next;
};

And now, you don't have a chicken & egg problem any longer; just start from an instantiation of EmptyList<T>.

Note: the presence of _kind in the base class is not that OO, but it makes things closer to the functional example by tagging which alternative is used.

How does the list end?

You will need at least two types: the end and not. You also need lifetime management. And either runtime or static knowledge of which type.

A completely static implementation could be done, where each node is its own type that knows how far it is to the end.

Or you could just have an unintialized buffer, and create elements off it in reverse order.

A circle is also possible. Make the first reference refer to the last element you construct.