title: What is the idiomatic way to write a linked list with a tail pointer?
body: <p>As a learning project for Rust, I have a very simple (working, if incomplete) implementation of a singly linked list.  The declaration of the structs looks like this:</p>
  
  <pre><code>type NodePtr&lt;T&gt; = Option&lt;Box&lt;Node&lt;T&gt;&gt;&gt;;
  
  struct Node&lt;T&gt; {
      data: T,
      next: NodePtr&lt;T&gt;,
  }
  
  pub struct LinkedList&lt;T&gt; {
      head: NodePtr&lt;T&gt;,
  }
  </code></pre>
  
  <p>Implementing <code>size</code> and <code>push_front</code> were both reasonably straight-forward, although doing size iteratively did involve some "fighting with the borrow checker."</p>
  
  <p>The next thing I wanted to try was adding a <code>tail</code> pointer to the <code>LinkedList</code> structure. to enable an efficient <code>push_back</code> operation.  Here I've run into a bit of a wall.  At first I attempted to use <code>Option&lt;&amp;Box&lt;Node&lt;T&gt;&gt;&gt;</code> and then <code>Option&lt;&amp;Node&lt;T&gt;&gt;</code>.  Both of those led to sprinkling <code>'a</code>s everywhere, but still eventually being unable to promise the lifetime checker that <code>tail</code> would be valid.</p>
  
  <p>I have since come to the tentative conclusion that it is impossible with these definitions: that there is no way to <em>guarantee</em> to the compiler that <code>tail</code> would be valid in the places that I think it is valid.  The only way I can possibly accomplish this is to have all my pointers be <code>Rc&lt;_&gt;</code> or <code>Rc&lt;RefCell&lt;_&gt;&gt;</code>, because those are the only safe ways to have two things pointing at the same object (the final node).</p>
  
  <p>My question: is this the correct conclusion?  More generally: what is the idiomatic Rust solution for unowned pointers inside data structures?  To my mind, reference counting seems awfully heavy-weight for something so simple, so I think I must be missing something.  (Or perhaps I just haven't gotten my mind into the right mindset for memory safety yet.)</p>