A linked list is the most honest data structure for understanding Rust's ownership model. With Vec everything is hidden away; here every node holds its neighbor itself, and the compiler will nitpick every single reference. We'll build our own LinkedList<T> from scratch: start safe with Box, get push_front/pop_front and three iterators working, then hit a wall — and deliberately move to raw pointers and unsafe to understand why the standard library does exactly this.

A node that doesn't fit inside itself

A list is a chain of nodes, and a node stores data plus a reference to the next one. The naive version looks obvious — and doesn't compile.

struct Node<T> {
    data: T,
    next: Node<T>,
}

The compiler can't compute the size of Node: to know the size of Node, it needs the size of the next field, which is another Node — infinite recursion. The type literally contains itself with no indirection, so there's no number of bytes to allocate for it.

The fix is a pointer. We wrap next in a Box.

struct Node<T> {
    data: T,
    next: Box<Node<T>>,
}

Box puts the value on the heap and itself occupies exactly one usize on the stack — just an address. Now the size of Node is known: the data plus one pointer. But we still can't create such a node — the next field is mandatory, so every node must have a next one, and the chain has nowhere to end.

We express the terminal node with Option.

struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}

None is the end of the list — the last node points at no one. The Option<Box<…>> nesting starts to grate, so we hide it behind a type alias.

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    data: T,
    next: Link<T>,
}

Link<T> reads as "a reference to the next node, which may not exist." LinkedList<T> itself is now built the same way — a single head field of type Link<T>, pointing at the first node or at None for an empty list.

push and pop: shuffling ownership via take

Adding to the head of the list comes down to "where do we put the old head." In Rust you can't simply leave a field half-empty while you build a new node: the compiler won't let you pull a value out and leave a hole. So we take the old head with take.

pub fn push_front(&mut self, data: T) {
    let next = self.head.take();
    let head = Box::new(Node { data, next });
    self.head = Some(head);
}

take substitutes None into the head field and returns whatever was there before — in one move, with no copies. The old head becomes the next field of the new node, the new node moves into a Box on the heap, and head now points at it. Popping from the head is the mirror operation.

pub fn pop_front(&mut self) -> Option<T> {
    self.head.take().map(|node| {
        self.head = node.next;
        node.data
    })
}

Again take grabs the head and leaves None. On an empty list there was None, and map does nothing — the caller gets None instead of a panic. On a non-empty one we move head to the next node and hand data out. The old Box goes out of scope at the end of the closure and frees itself — while we're on safe pointers, that's nothing to think about.

An iterator over references: borrow, don't take

The most common traversal is to walk the elements while destroying nothing. That's an iterator handing out &T. We give it a dedicated struct with a cursor.

pub struct Iter<'a, T> {
    current: Option<NonNull<Node<T>>>,
    _list: &'a LinkedList<T>,
}

The current field is a pointer to the node we're standing on. And _list is a borrow of the list itself: it does nothing at runtime, but it ties the lifetime 'a to the list. While the iterator is alive, the list is borrowed, and Rust won't let it be mutated or dropped out from under the iterator. The iter method starts the cursor at the head.

pub fn iter(&self) -> Iter<'_, T> {
    Iter {
        current: self.head.clone(),
        _list: self,
    }
}

The '_ notation means "take the lifetime from &self" — the iterator won't outlive the list it came from. The traversal step itself lives in the Iterator trait.

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

    fn next(&mut self) -> Option<Self::Item> {
        self.current.map(|node| unsafe {
            let node = node.as_ref();
            self.current = node.next.clone();
            &node.data
        })
    }
}

Item is declared as &'a T — a reference with the same lifetime as the list, so it's guaranteed valid for as long as the list lives. Each next takes the current node, advances current to its next, and returns a reference to data. By implementing Iterator we get its whole arsenal for free — map, filter, collect — on our list.

An iterator that takes the values

Sometimes the list needs to be "eaten" — walked while pulling each element out by value. That's IntoIter, and it's almost embarrassingly simple: just wrap the list itself.

pub struct IntoIter<T>(LinkedList<T>);

impl<T> Iterator for IntoIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.pop_front()
    }
}

Here Item is T, not a reference: we hand over ownership of the element. And next writes no traversal logic at all — it just calls pop_front. The list already knows how to pop the head and move head, so eating it whole is calling pop_front until it returns None. All that's left is to tie the type to the list with the IntoIterator trait.

impl<T> IntoIterator for LinkedList<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;

    fn into_iter(self) -> Self::IntoIter {
        IntoIter(self)
    }
}

into_iter takes self by value — the list is consumed and no longer available. In return, for x in list now works: the for loop calls exactly into_iter under the hood. One trait — and our hand-rolled list behaves like a native container.

Why safe pointers aren't enough

So far everything has rested on Box, and the list has been singly linked: each node owns the next one. But a real doubly linked list wants two parties pointing at one node — the previous and the next. And Box is sole ownership; it allows no two owners for one value.

The obvious workaround is shared ownership via Rc. But with two references, Rc::get_mut stops giving mutable access — it only works when there's a single copy. We pile a RefCell on top to bring mutability back — but borrow_mut returns no longer a reference but a RefMut wrapper, and we'd have to rework the iterator signatures around it. The Rc<RefCell<…>> construction sprawls and drags borrow checks into runtime.

The honest way out is to take control ourselves and store nodes as raw pointers. We swap Box for NonNull in the alias.

type Link<T> = Option<NonNull<Node<T>>>;

NonNull is a raw pointer with one guarantee: it's never null. It carries no ownership at all — the pointer is no longer responsible for freeing what it looks at. From this point on, memory is our concern, and the compiler stops helping us.

Raw pointers: leak out, from_raw back

To get a raw pointer out of a Box, we deliberately "lose" the allocation. In push_front that's done by Box::leak.

pub fn push_front(&mut self, data: T) {
    let next = self.head.take();
    let head = Box::new(Node { data, next });
    let head_ptr = NonNull::from(Box::leak(head));
    self.head = Some(head_ptr);
}

Box::leak consumes the Box and hands back a mutable reference to its contents — a controlled leak: no one owns the value anymore and its destructor won't fire on its own. NonNull::from turns that reference into our raw pointer. The node lives on the heap, but now only we know when to free it. The other side is in pop_front, where ownership must be brought back.

pub fn pop_front(&mut self) -> Option<T> {
    self.head.take().map(|node| unsafe {
        let node = Box::from_raw(node.as_ptr());
        self.head = node.next;
        node.data
    })
}

as_ptr extracts the raw pointer from the NonNull, and Box::from_raw rebuilds a Box from it — getting ordinary ownership back: on exit from the closure this Box frees itself. The closure is marked unsafe because from_raw takes us at our word: the pointer is valid, points at a real Node, and isn't owned by anyone else. In our case that's true — we created the node ourselves and are popping it ourselves right now — but it's we, not the compiler, who give the guarantee.

Drop without leaks, even on panic

Since we did a leak, the compiler no longer knows about the memory under the nodes and won't insert its release itself. The test will pass — and memory will leak anyway. So we have to write the cleanup by hand in the Drop trait.

impl<T> Drop for LinkedList<T> {
    fn drop(&mut self) {
        while self.pop_front().is_some() {}
    }
}

The loop just pops the head until the list is empty; each pop_front rebuilds a Box and frees the node. That's almost enough — but there's a subtlety. If T itself panics in its own drop, the loop breaks halfway and the tail of the list leaks. To finish the cleanup even after a panic, we introduce a little DropGuard.

struct DropGuard<'a, T>(&'a mut LinkedList<T>);

impl<'a, T> Drop for DropGuard<'a, T> {
    fn drop(&mut self) {
        while self.0.pop_front().is_some() {}
    }
}

DropGuard holds a mutable reference to the list, and its own drop is the same cleanup loop. The trick is that while unwinding the stack after a panic, Rust calls drop on every local, including our guard. It remains to wire this up correctly in the list's Drop.

let guard = DropGuard(self);
while guard.0.pop_front().is_some() {}
std::mem::forget(guard);

The main loop runs through guard. If there's a panic inside — the guard is local, its drop fires during stack unwinding and finishes popping the remaining nodes. If the loop reached the end normally, the list is already empty and a second pass is pointless, so we call std::mem::forget(guard) — it tells the compiler not to run the destructor. The DropGuard itself lives on the stack, so its memory is freed when the function returns, with no drop needed.

Where to grow next

This is a working singly linked list with manual memory management — a solid base for several obvious continuations.

  • Double linking. Give nodes a prev field and the list a tail pointer — exactly the case we went to NonNull for: a node is now looked at from two sides.
  • Two-way traversal. Implement DoubleEndedIterator with a next_back method to iterate from the tail too.
  • A mutating iterator. IterMut, handing out &mut T, is the trickiest of the three on lifetimes.
  • PhantomData. Hint to the compiler that the list logically owns its Ts, even though it stores them behind raw pointers.

Why build this

A linked list is the smallest program that rubs your nose in the very heart of Rust: ownership, borrowing, lifetimes, and the line past which unsafe stops being a slur and becomes a tool. With your own hands you walked from Box, where the compiler pads the corners, to raw pointers, where you pad them yourself — and along the way you understood exactly what each safe abstraction costs. After that the unsafe internals of Vec and VecDeque from the standard library read not as black magic but as familiar code.