Push

Pushing onto the front: allocate a new node, point its next at the current head, swing the head pointer to the new node. Two lines of C. In Rust the borrow checker has notes.

1. 01
   First attempt is the C translation. The compiler refuses: you cannot move out of self.head while you only hold a &mut self.

   pub fn push(&mut self, elem: i32) {
       let new_node = Box::new(Node {
           elem,
           next: self.head,   // error: cannot move out of borrowed content
       });
       self.head = Link::More(new_node);
   }

2. 02
   The classic move-out problem in safe Rust. The fix is std::mem::replace: it takes a &mut T and a replacement value, swaps them in place, and hands the old value back to you by value. The location is never invalid.

   use std::mem;
   
   pub fn push(&mut self, elem: i32) {
       let new_node = Box::new(Node {
           elem,
           next: mem::replace(&mut self.head, Link::Empty),
       });
       self.head = Link::More(new_node);
   }

3. 03
   Compiles. Costs one allocation per push (the Box::new). The temporary Link::Empty is a single tag write — basically free. Notice we never wrote unsafe.

   let mut list = List::new();
   list.push(1);
   list.push(2);
   list.push(3);
   // head -> 3 -> 2 -> 1 -> Empty