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

2020-03-03 06:56发布

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

7条回答
爷的心禁止访问
2楼-- · 2020-03-03 07:34

I might be off the mark, but this works

    struct Node;
struct Node {

    using link = std::reference_wrapper<Node>;

    Node( char data_  =  0) 
        : next({*this})
        , data( data_ == 0 ? '?' : data_ ) 
    {}

    bool is_selfref() const noexcept {
        return (this == & next.get());
    }

    char data;
    link next;
};

The usual tests

 Node A('A');     
 Node B('B');     
 Node C('C');     
 assert( A.is_selfref() == B.is_selfref() == C.is_selfref());

 A.next = B;  B.next = C;

 assert(! A.is_selfref() && ! B.is_selfref() );
 assert(  C.is_selfref() );

 assert( 'A' == A.data );
 assert( 'B' == A.next.get().data );
 assert( 'C' == A.next.get().next.get().data );

 // C.next == C

 // for those who feel safe seeing the END
 Node END(127);
 C.next = END;

Of course, as long as all Node's stay in the scope we are all ok here. Otherwise not. Strange and wonderful. Very limited utility?

查看更多
登录 后发表回答