What is the idiomatic way to write a linked list with a pointer to a tail?

Question

As a training project for Rust, I have a very simple (working, if not complete) implementation of a singly linked list. Declaration of structures is as follows:

type NodePtr<T> = Option<Box<Node<T>>>; struct Node<T> { data: T, next: NodePtr<T>, } pub struct LinkedList<T> { head: NodePtr<T>, } 

The implementation of size and push_front were fairly straightforward, although size was iteratively related to some “borrower struggles”.

The next thing I wanted to try was to add a tail pointer to the LinkedList structure. for effective work push_back . Here I came across a wall. First I tried to use Option<&Box<Node<T>>> , and then Option<&Node<T>> . Both of them led to the fact that they were strewn down everywhere, but still could not promise that the check of the lifetime would be tail .

Since then, I have come to the preliminary conclusion that with these definitions it is impossible: there is no way to guarantee to the compiler that tail will be valid in those places that I think are valid. The only way I can do this is to have all my pointers be Rc<_> or Rc<RefCell<_>> , because these are the only safe ways to have two things pointing to the same object (final node).

My question is: is this the correct conclusion? More generally: what is the idiomatic Rust solution for unpublished pointers inside data structures? In my opinion, link counting seems terribly difficult for something so simple, so I think I'm missing something. (Or maybe I haven't gotten to the right mindset for memory security.)

Answer 1

Yes, if you want to write a singly linked list with a pointer to a tail, you have three options:

• Safe and Mutable: use NodePtr = Option<Rc<RefCell<Node<T>>>>
• Safe and immutable: use NodePtr = Option<Rc<Node<T>>>
• Unsafe and Mutable: use tail: *mut Node<T>

*mut will be more efficient, and it does not look like Rc will actually prevent you from creating completely pointless states (as you correctly inferred). It just ensures that they don't call segfaults (and with RefCell, it can still cause runtime crashes though ...).

Ultimately, any linked list that is more complex than vanilla with a single link has a property history that is too complex to safely and efficiently encode in the Rust ownership system (this is not a tree). I personally prefer just to embrace insecurity at this moment and relying on unit tests to get to the finish line in one piece (why write a suboptimal data structure ...?).