Layout

The shape is what you'd write in C: a struct with front and back node pointers and a length. The Rust differences are the choice of pointer type (NonNull<Node<T>> instead of *mut Node<T>) and a zero-sized marker field that exists purely to inform the compiler about ownership.

1. 01
   NonNull<T> is *mut T plus a guarantee that the bit pattern is never zero. Two consequences: the compiler can apply the null-pointer optimization so Option<NonNull<T>> is one pointer wide (the None is the all-zero bit pattern), and you opt into covariance over T instead of the invariance you'd inherit from *mut T. We pay nothing at runtime for either.

   use std::marker::PhantomData;
   use std::ptr::NonNull;
   
   pub struct LinkedList<T> {
       front: Option<NonNull<Node<T>>>,
       back: Option<NonNull<Node<T>>>,
       len: usize,
       _marker: PhantomData<Box<Node<T>>>,
   }
   
   struct Node<T> {
       front: Option<NonNull<Node<T>>>,
       back: Option<NonNull<Node<T>>>,
       elem: T,
   }

2. 02
   PhantomData<Box<Node<T>>> is a zero-sized field whose type encodes the lie we want the compiler to believe: this struct owns Node<T> values on the heap. That gets us the right variance over T (covariant) and, crucially, the right dropck signal — the compiler will treat our list as if it owns and drops Node<T> when the list is dropped, even though our actual fields are raw pointers.

   // these are zero bytes at runtime:
   use std::mem::size_of;
   assert_eq!(size_of::<PhantomData<Box<i32>>>(), 0);
   
   // the whole list is three pointer-sized words:
   assert_eq!(
       size_of::<LinkedList<i32>>(),
       3 * size_of::<usize>(),
   );

3. 03
   Why not *mut Node<T> directly? Two reasons. (1) *mut T is invariant in T, which we don't want for an owning collection — LinkedList<&'static str> should be usable where LinkedList<&'a str> is expected. (2) Option<*mut T> is two words because *mut T permits a null bit pattern. NonNull<T> plus Option plus PhantomData is the canonical recipe.

   impl<T> LinkedList<T> {
       pub const fn new() -> Self {
           LinkedList {
               front: None,
               back: None,
               len: 0,
               _marker: PhantomData,
           }
       }
   }