Basics

First pass at push and pop. We keep the Box-owned chain and update tail whenever we extend the back. The compiler is happy. The program is wrong, but not in a way the compiler will diagnose.

1. 01
   push_back allocates a node, stashes its address in a local *mut, then either splices it onto the empty list or hangs it off the previous tail. The deref of self.tail (when nonempty) requires unsafe.

   pub fn push_back(&mut self, elem: T) {
       let mut new_node = Box::new(Node { elem, next: None });
       let raw_tail: *mut Node<T> = &mut *new_node;
   
       if self.tail.is_null() {
           self.head = Some(new_node);
       } else {
           unsafe { (*self.tail).next = Some(new_node); }
       }
       self.tail = raw_tail;
   }

2. 02
   pop_front is the safe-Rust pop from chapter 2 with one extra wrinkle: when we pop the last node, self.tail becomes a dangling pointer to freed memory. Reset it to null in that case.

   pub fn pop_front(&mut self) -> Option<T> {
       self.head.take().map(|head| {
           let head = *head;
           self.head = head.next;
           if self.head.is_none() {
               self.tail = ptr::null_mut();
           }
           head.elem
       })
   }

3. 03
   It compiles, runs, passes a hand-written test. The bug is in push_back: &mut *new_node produces a &mut Node<T>, we cast it to *mut Node<T>, then we move new_node into self.head or into the previous tail's next. The act of moving the box invalidates outstanding references derived from it, and the next deref of raw_tail is reading through a stale tag.

   let mut q = List::new();
   q.push_back(1);
   q.push_back(2);
   q.push_back(3);
   assert_eq!(q.pop_front(), Some(1));
   assert_eq!(q.pop_front(), Some(2));
   assert_eq!(q.pop_front(), Some(3));
   assert_eq!(q.pop_front(), None);
   // passes. and yet.