How are Options<> stored in memory?

[kay_kay]

I'm trying to understand a simple singly linked list in Rust but having a hard time understanding the references.

The below is a code I found for Iterating a List.

pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

impl<T> List<T> {
    pub fn iter<'a>(&'a self) -> Iter<'a, T> {
        Iter { next: self.head.as_ref().map(|node| &**node) }
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_ref().map(|node| &**node);
            &node.elem
        }) 
    }
}

Full code available here: Final Code - Learning Rust With Entirely Too Many Linked Lists

I would like to know how Option, Option<&T> (i.e., Option.as_ref() from above code snippet) and Option<Box> are stored in memory to get a better understanding of the List code.

[chrisd]

It depends. To recap, Option means it can be some type or nothing (aka None, as Rust calls it). So you need a value that means None. How it does this is technically an implementation detail, although it can be important.

Depending on how this is optimized, this might mean Option<T> is represent as, for example, (bool, T). Then to check if the Option is Some value or None, the bool is checked first.

In the case of Option<&T> there's an optimization because references in Rust can never be null. So instead of using a bool it can just test for the zero value to decide between Some or None.

In short, Option<&T> is represented the same as &T in memory except that Option<&T> can be null and &T can't.

[RustyYato]

The same optimization also packs None in Option<Box<_>> into null because Box is never null.

[troiganto]

In case you need a googlable name, this trick is called niche-filling optimization in Rust.