title: Is there a way to build a structure with cyclic links without runtime overhead?
body: <p>I am trying to implement a cyclic linked data structure in Rust. My <code>Node</code>s are defined as:</p>
  
  <pre><code>#[derive(Debug)]
  enum Node&lt;'a&gt; {
      Link(&amp;'a Node&lt;'a&gt;),
      Leaf,
  }
  </code></pre>
  
  <p>I am trying to build a minimal structure like this (extra brackets for better lifetime visibility):</p>
  
  <pre><code>fn main() {
      let placeholder = Node::Leaf;
      {
          let link1 = Node::Link(&amp;placeholder);
          {
              let link2 = Node::Link(&amp;link1);
              println!("{:?}", link2);
          } // link2 gets dropped
      } // link1 gets dropped
  }
  </code></pre>
  
  <p>This works, but now I don't know how to replace the placeholder with a reference to <code>link2</code> to "close the cycle". I tried this, but it doesn't work because I can't assign to <code>link1</code>, which is borrowed the line above, and because <code>link2</code> would go out of scope while it's still referenced by <code>link1</code>:</p>
  
  <pre><code>let placeholder = Node::Leaf;
  {
      let mut link1 = Node::Link(&amp;placeholder);
      {
          let link2 = Node::Link(&amp;link1);
          link1 = Node::Link(&amp;link2);
          println!("{:?}", link2);
      } // link2 gets dropped
  } // link1 gets dropped
  </code></pre>
  
  <pre class="lang-none prettyprint-override"><code>error: `link2` does not live long enough
    --&gt; src/main.rs:15:9
     |
  13 |             link1 = Node::Link(&amp;link2);
     |                                 ----- borrow occurs here
  14 |             println!("{:?}", link2);
  15 |         } // link2 gets dropped
     |         ^ `link2` dropped here while still borrowed
  16 |     } // link1 gets dropped
     |     - borrowed value needs to live until here
  
  error[E0506]: cannot assign to `link1` because it is borrowed
    --&gt; src/main.rs:13:13
     |
  12 |             let link2 = Node::Link(&amp;link1);
     |                                     ----- borrow of `link1` occurs here
  13 |             link1 = Node::Link(&amp;link2);
     |             ^^^^^^^^^^^^^^^^^^^^^^^^^^ assignment to borrowed `link1` occurs here
  </code></pre>
  
  <p>I could try to avoid these lifetime issues by using <code>Rc</code>s, but that sounds like it would defeat the purpose of Rust's 0-runtime-cost lifetime management.</p>
  
  <p>Another attempt of putting all nodes into a <code>Vec</code> and only taking direct references to that didn't work either:</p>
  
  <pre><code>use std::ops::IndexMut;
  
  let mut store = Vec::new();
  store.push(Node::Leaf);
  store.push(Node::Link(&amp;store[0]));
  store.push(Node::Link(&amp;store[1]));
  *store.index_mut(1) = Node::Link(&amp;store[2]);
  </code></pre>
  
  <p>Because I can't change any nodes without mutably borrowing them, but they have all been immutably borrowed already.</p>
  
  <pre class="lang-none prettyprint-override"><code>error[E0502]: cannot borrow `store` as immutable because it is also borrowed as mutable
    --&gt; src/main.rs:12:28
     |
  12 |     store.push(Node::Link(&amp;store[0]));
     |     -----                  ^^^^^    - mutable borrow ends here
     |     |                      |
     |     |                      immutable borrow occurs here
     |     mutable borrow occurs here
  
  error[E0502]: cannot borrow `store` as mutable because it is also borrowed as immutable
    --&gt; src/main.rs:13:5
     |
  12 |     store.push(Node::Link(&amp;store[0]));
     |                            ----- immutable borrow occurs here
  13 |     store.push(Node::Link(&amp;store[1]));
     |     ^^^^^ mutable borrow occurs here
  14 |     *store.index_mut(1) = Node::Link(&amp;store[2]);
  15 | }
     | - immutable borrow ends here
  
  error[E0502]: cannot borrow `store` as immutable because it is also borrowed as mutable
    --&gt; src/main.rs:13:28
     |
  13 |     store.push(Node::Link(&amp;store[1]));
     |     -----                  ^^^^^    - mutable borrow ends here
     |     |                      |
     |     |                      immutable borrow occurs here
     |     mutable borrow occurs here
  
  error[E0502]: cannot borrow `store` as mutable because it is also borrowed as immutable
    --&gt; src/main.rs:14:6
     |
  12 |     store.push(Node::Link(&amp;store[0]));
     |                            ----- immutable borrow occurs here
  13 |     store.push(Node::Link(&amp;store[1]));
  14 |     *store.index_mut(1) = Node::Link(&amp;store[2]);
     |      ^^^^^ mutable borrow occurs here
  15 | }
     | - immutable borrow ends here
  </code></pre>
  
  <p>Is there a way to have such a structure with cyclic links without runtime overhead, for example with pure references like I tried? I'm fine with additional memory cost, like a backing <code>Vec</code> holding ownership to all nodes.</p>