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

Question

Suppose I want to create an unmodifiable linked-list (i.e. it can only be traversed, no nodes can be added or removed once it was initially created). This could be easily implemented by:

struct ListNode
{
  int value;
  ListNode* nextNode;
}

My question is .... Would it be possible to use references instead of pointers?

struct ListNodeWithRefs
{
  int value;
  ListNodeWithRefs &nextNode;
}

I am not sure it would provide any performance gain at all but ... this question popped up while coding and my answer so far is no but I could be missing something.

In principle, nothing prevents you from using references, and constructing list elments like this:

ListNodeWithRefs::ListNodeWithRefs(ListNodeWithRefs &next):
  nextNode(next)
{}

But there is a chicken and egg problem because next also enforces its next element to exist at its creation and so on ...

Note: I think my question can also be applied to defining the list as:

struct ListNodeConst
{
  int value;
  const ListNode* nextNode;
}

Answer 1

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.