Basics

No push/pop — those imply mutation. The persistent vocabulary is prepend(elem) and tail(), both of which take &self and return a brand-new List that shares structure with the old one. head() returns Option<&T> for read access. Every method is non-mutating; the borrow checker has no work to do.

1. 01
   new and prepend: build a node whose next is a clone of self.head. Rc::clone of an Option<Rc<_>> is just self.head.clone() — Option::clone calls Rc::clone on the inner handle, which is a refcount bump, not a deep copy.

   impl<T> List<T> {
       pub fn new() -> Self {
           List { head: None }
       }
   
       pub fn prepend(&self, elem: T) -> List<T> {
           List {
               head: Some(Rc::new(Node {
                   elem,
                   next: self.head.clone(),
               })),
           }
       }
   }

2. 02
   tail returns the rest of the list. self.head.as_ref() borrows the Option<Rc<Node<T>>> as Option<&Rc<Node<T>>>; .and_then extracts node.next.clone() if there's a head, or None otherwise. Net cost: at most one refcount bump.

   impl<T> List<T> {
       pub fn tail(&self) -> List<T> {
           List {
               head: self.head.as_ref().and_then(|node| node.next.clone()),
           }
       }
   
       pub fn head(&self) -> Option<&T> {
           self.head.as_ref().map(|node| &node.elem)
       }
   }

3. 03
   Notice every method takes &self. There's no &mut self anywhere — the data structure is immutable from the outside. prepend and tail produce values; the caller decides whether to bind them to a new name or shadow the old one. Sharing is free at the API level: clone the list itself (via Rc::clone if you wrap it, or by re-running prepend) and you have two persistent views.

   let list = List::new().prepend(1).prepend(2).prepend(3);
   // list:    3 -> 2 -> 1 -> Nil
   
   let shorter = list.tail();
   // shorter: 2 -> 1 -> Nil
   // list is still 3 -> 2 -> 1 -> Nil; both lists alive.
   
   assert_eq!(list.head(),    Some(&3));
   assert_eq!(shorter.head(), Some(&2));