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

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

No. Reasons:

1. You cannot insert a node if nextNode is a reference.
2. What should nextNode refer to if this is list tail?

Answer 2

That was quite tricky but this worked :

#include <iostream>
#include <typeinfo>

class Last {
  public:

    int x;
    int last;

    Last(int i) {
      std::cout << "parent constructor(" << i << ")\n";
      x = i;
      last = 1;
    }
};

struct fourptr {
    int v1, v2;
    void *p1, *p2;
    };

class chain : public Last {
  public:

    chain(int i) : Last(i) {
    std::cout << "child constructor(" << i << ")\n";
    last = 0;
    }

    void viewandnext() {
      struct fourptr *fp = (struct fourptr *) this;
      std::cout << x << ", this = " << this
                << ", sizeof *this = "<< sizeof * this
                << ", * this = {" << fp->v1 << ", " << fp->v2 << ", "
                << fp->p1 << ", " << fp->p2 << "}"
                << "\n";
      if (last == 0) ((chain &)next).viewandnext();
    }

  Last & fn(int x) {
    Last * e = (x>0) ? new chain(x-1) : new Last(x-1);
    return *e;
  }

    Last & next = fn(x); // This is not a pointer but a reference
};



int main(void) {
  chain &l = *(new chain(8));
  std::cout << "sizeof l = "<< sizeof l << "\n";
  l.viewandnext();
}

Answer 3

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);
}

Answer 4

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.

Answer 5

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.

Answer 6

As @Vlad said, the problem with references is that you will need a final object. The good news is that, in principle, you can still have a cyclic list, if you have a use for it. This is a fundamental thing, if the "next" element is a non-nullable reference means that there is always a next element, that is, the list is either infinite or, more realistically, it closes on itself or into another list.

Taken the exercise further is quite interesting and strange. Basically the only thing that seems to be possible is to defined the equivalent of the a node (which also represents the list).

template<class T>
struct node{
    T value; // mutable?
    node const& next;
    struct circulator{
        node const* impl_;
        circulator& circulate(){impl_ = &(impl_->next); return *this;}
        T const& operator*() const{return impl_->value;}
        friend bool operator==(circulator const& c1, circulator const& c2){return c1.impl_ == c2.impl_;}
        friend bool operator!=(circulator const& c1, circulator const& c2){return not(c1==c2);}
    };
    circulator some() const{return circulator{this};}
};

The elements have to live in the stack and the list is static (well, references are not rebindable anyway) and the links have to be const references! Eventually the value can be made then mutable apparently (probably safe?). (At this point one wonders how is this different from a stack array references by a modulo indices.)

There is only one way to construct the node/list object, that is to close it with itself (or with other preexising node). So the resulting list are either circular or "rho" shape.

    node<int> n1{5, {6, {7, n1}}};
    auto c = n1.some();
    cout << "size " << sizeof(node<int>) << '\n';
    do{
        cout << *c << ", ";
        c.circulate();
    }while(c != n1.some()); //prints 5, 6, 7

I wasn't able to make a node that is not trivially constructible (aggregate?). (Adding any sort of basic constructor produced segmentation faults for a reason I can't understand, both in gcc and clang). I wasn't able to encapsulate the node in a "container" object for the same strange reason. So making an object that could be constructed like this was impossible to me:

circular_list<int> l{1,2,3,4}; // couldn't do this for obscure reasons

Finally, since a proper container cannot be constructed it is not clear what is the semantics of this object, for example when two "lists" are equal? what doesn't mean to assign? or assign between list of different sizes?

It is a quite paradoxical object, with no general value or reference semantics apparently.

Any comments or improvements are welcomed!