Layout

A doubly-linked list needs nodes that point at each other in both directions. Two nodes referencing one another means neither one can uniquely own the other — single-owner Box is out. We need shared ownership and mutation through the share, which is Rc<RefCell<T>>.

1. 01
   Rc<T> from Chapter 3 gave us shared ownership but only &T access — read-only. To mutate the contents through an Rc, you wrap the inside in RefCell<T>. RefCell is interior mutability: it lets you take a &mut to its contents through a & reference, by tracking borrows at runtime instead of compile time. Think shared_ptr<mutex<T>> without the locking — same shape, single-threaded, panic instead of deadlock.

   use std::cell::RefCell;
   use std::rc::Rc;
   
   pub struct List<T> {
       head: Link<T>,
       tail: Link<T>,
   }
   
   type Link<T> = Option<Rc<RefCell<Node<T>>>>;
   
   struct Node<T> {
       elem: T,
       next: Link<T>,
       prev: Link<T>,
   }

2. 02
   The Link<T> alias hides the triple wrap. Every link is optional (might be the end), counted (shared between the neighbouring node and possibly the list itself), and cell-wrapped (so the neighbour can rewrite it later). At runtime each link is one fat pointer plus an enum tag.

   impl<T> List<T> {
       pub fn new() -> Self {
           List { head: None, tail: None }
       }
   }