From Box to raw pointers: building a real deque in Rust

The linked list is famously the data structure Rust makes hard. That's exactly why it's worth building one: a list forces you through ownership, recursion, lifetimes, and unsafe in one tidy package. We'll grow a toy stack into a production-shaped, doubly-linked deque with three iterator types — one small piece at a time — and understand every decision along the way.

The core idea in one sentence

A list is a chain of heap-allocated nodes, each holding a value and a pointer to its neighbours; the container just remembers where the chain starts and ends.

Step one: a node that can even compile

The obvious node — "data, plus the next node" — doesn't type-check. Write it the naive way first:

struct Node<T> {
    data: T,
    next: Node<T>, // recursive: infinite size
}

Node<T> would contain a Node<T> which contains a Node<T>, forever. The compiler lays out a struct by adding up the sizes of its fields, and here that sum never terminates — so it rejects the type outright. The error isn't a technicality; the value genuinely has no finite size.

The fix is indirection: put the next node behind a pointer, which is a fixed-size address no matter how big the thing it points to is.

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

Box<T> is an owning heap pointer — one machine word, regardless of T. Wrapping it in Option lets the chain stop: None means "end of chain", Some(box) means "there's another node". Now the size is finite and the type compiles.

That Option<Box<Node<T>>> is going to appear in every field and signature, so give it a name:

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

This is a pure type alias — it compiles to the identical type, costs nothing, and just spares you from retyping the nest. From here on, "a link" means "maybe a pointer to the next node".

A stack from two moves

The public container owns the head of the chain, and a stack is just two operations on that head: push_front and pop_front. Both are O(1). Start with the push:

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

The first line is the whole trick: take() moves the old head out and leaves None in its place. The new node then adopts that old head as its next, and we box it up as the new head. So pushing is "unhook the front, build a node in front of it, hook it back on".

Now the mirror image, pop_front:

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

The ? does double duty: it pulls the boxed head out and, on an empty list, returns None for us. We then promote the second node to head and hand back the data. When the popped Box goes out of scope at the end, its heap allocation is freed automatically.

The hero in both methods is Option::take(). You can't move a field out from behind &mut self directly — Rust refuses to leave self in a half-valid state mid-move. take() swaps in None and hands you the old value, so ownership transfers cleanly with no borrow conflict.

Iterators: read, mutate, consume

Idiomatic Rust collections offer three flavours of iteration, and they differ only in what each next yields:

list.iter()      // -> &T      read
list.iter_mut()  // -> &mut T  modify
list.into_iter() // -> T       consume

iter borrows each element so you can read it, iter_mut borrows mutably so you can change it in place, and into_iter takes ownership and empties the list as it goes. Same walk, three different things handed back.

The shared iterator carries a cursor — a reference to the current link — and advances it down the chain:

fn next(&mut self) -> Option<&'a T> {
    let node = self.current.as_deref()?;
    self.current = &node.next;
    Some(&node.data)
}

as_deref() turns &Option<Box<Node>> into Option<&Node> without moving anything out of the box — it just reborrows through it. The ? stops us at the end of the chain, we step the cursor to the next link, and yield a reference to this node's data. Nothing is consumed, so you can iterate as many times as you like.

The owning iterator is almost free. Wrap the list in a newtype and delegate to the pop we already wrote:

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

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        self.0.pop_front()
    }
}

Each next just pops the front and returns the owned value, so the iterator drains the list one element at a time. Because pop_front already handles the empty case, there's nothing else to write. Implement IntoIterator for the list and for x in list { ... } works — that loop is literally sugar for into_iter().

Why Box runs out of road

To support O(1) operations at both ends, each node needs a prev pointer too, so we can walk and splice backward as cheaply as forward. But this breaks Box. A Box means unique ownership — exactly one owner — and a doubly-linked node is owned by two neighbours at once: its predecessor's next and its successor's prev would both have to own it. Box simply can't express two owners.

So we drop down to raw pointers:

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

NonNull (from the standard library's ptr module) is a non-null raw pointer that doesn't own anything — it's just an address, and it's freely Copy, so two neighbours can each hold one to the same node without anyone "owning" it. The Option still encodes "end of chain" as before, only now the present case is a bare pointer instead of a box.

Nobody owns the node, so nobody frees it for us — we allocate by hand. The pattern is "box it, then deliberately forget the box":

let node = Box::new(Node {
    data, prev, next: None,
});
let ptr = Some(NonNull::from(Box::leak(node)));

Box::leak heap-allocates the node and then hands back a plain reference, promising never to free it — exactly the leak we want, because we will free it later with Box::from_raw. NonNull::from turns that reference into the raw pointer we store. This is manual memory management inside Rust's type system: every dereference from here on is an unsafe block, a written promise that we'll uphold our invariants.

The invariant, and keeping it

The one rule of a doubly-linked list: for adjacent nodes A and B, A.next points to B and B.prev points to A. Every mutator exists to preserve that. Take push_back, the mirror of push_front — build it in stages. First, note whether we're starting from empty and allocate the new tail:

pub fn push_back(&mut self, data: T) {
    let was_empty = self.tail.is_none();
    let tail = Box::new(Node {
        data,
        prev: self.tail,
        next: None,
    });
    let tail_ptr =
        Some(NonNull::from(Box::leak(tail)));
    // … wire it up, fix the ends
}

The new node's prev is the current tail (it'll sit right after it) and its next is None (it's the new end). We grab was_empty up front because we're about to overwrite self.tail and will need to know the original state. Then we leak the box into a raw pointer, exactly as before.

Now wire the old tail's next forward to the new node — the half of the invariant the new node can't set itself:

if let Some(mut prev) = self.tail {
    // SAFETY: prev is the live current tail;
    // we hold &mut self.
    unsafe { prev.as_mut().next = tail_ptr };
}

This is unsafe because we're dereferencing a raw pointer we ourselves allocated, and the SAFETY note records why it's sound: prev is the current tail, so it's alive, and &mut self means nobody else is touching the list. If the list was empty there's no predecessor to update, so the if let simply skips.

Finally, fix up the container's own ends and the length:

self.tail = tail_ptr;
if was_empty {
    self.head = tail_ptr;
}
self.len += 1;

The new node is unconditionally the tail; it's also the head only if the list was empty (one element is both ends at once). That self.len += 1 is easy to overlook but load-bearing: a len field updated on every push and pop turns length queries from O(n) walks into O(1) reads. Miss it in one of the four mutators and the count silently drifts — a classic latent bug.

Cleaning up without leaking

Raw pointers don't free themselves, so we must implement Drop to drain the list and reclaim every node. The naive body is while self.pop_front().is_some() {} — pop until empty — but it has a hole: if an element's own destructor panics mid-drain, the loop unwinds and the remaining nodes leak. The standard-library fix (the same one Vec uses) is a drop guard. Define it inside drop:

impl<T> Drop for LinkedList<T> {
    fn drop(&mut self) {
        struct DropGuard<'a, T>(
            &'a mut LinkedList<T>,
        );
        // … guard's Drop, then drain
    }
}

DropGuard is a tiny wrapper holding a mutable borrow of the list, and its only job is to have a destructor of its own. The point is that this guard's drop will run during unwinding if anything panics — that's the lever we'll pull.

Give the guard a destructor that finishes the drain:

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

If a node's destructor panics while we're draining, unwinding drops this guard, and its drop resumes popping the rest of the list — so nothing leaks even on the panic path. It's the same pop-until-empty loop, just relocated somewhere unwinding is guaranteed to reach it.

Now the happy path: drain through the guard, then disarm it:

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

We pop through guard.0 so that if a panic strikes, the live guard takes over. If we reach the end normally, mem::forget drops the guard without running its destructor — the list is already empty, so re-draining would be wasted work. (A second panic during unwinding aborts the process, and there's genuinely nothing sane to do at that point.)

Iterating from both ends

With prev pointers and pop_back, every iterator can gain a backward gear via DoubleEndedIterator. The trick that makes it safe is a dual cursor: a front and a back pointer move toward each other, and a len counter — not a pointer comparison — decides when they've met. Here's next_back:

fn next_back(&mut self) -> Option<&'a T> {
    if self.len == 0 { return None; }
    let back = self.back?;
    // … step the cursor, yield the data
}

The len == 0 check is the stopping condition, and it comes first: once the two cursors have handed out every element between them, we're done, even though both pointers may still reference valid nodes. Only after that do we read the back cursor.

Then step the back cursor inward and yield:

// SAFETY: nodes live for 'a and aren't
// moved while iterating.
let node = unsafe { back.as_ref() };
self.back = node.prev;
self.len -= 1;
Some(&node.data)

We dereference the raw pointer (sound because the nodes outlive the iterator and nothing moves them mid-iteration), walk back one step toward the front via prev, decrement the count, and return the data. next from the other end is the mirror image, walking front forward.

For IterMut that len check is load-bearing for soundness, not just correctness: while len > 0, front and back are guaranteed to point at different nodes, so the two &mut T you hand out — one from each end — can never alias. Lean on a pointer comparison instead and a one-element range would yield the same node twice. With this in place, list.iter().rev(), iter_mut().rev(), and into_iter().rev() all work.

In production, you'd reach for Vec

Honest closing note: in real code you almost never want this. CPU caches love contiguous memory, and a Vec or VecDeque beats a pointer-chasing linked list for nearly every workload — that's why std's own LinkedList carries a "you probably don't want this" warning. From here you could add peek, splicing, or a Cursor API; but the real payoff is elsewhere.

Build this once and the abstract stops being abstract. You've felt why Box breaks down, held a raw pointer responsibly, written a SAFETY comment you actually believe, and made the borrow checker your collaborator instead of your opponent. That fluency is the thing you keep — and it transfers to every gnarly Rust type you'll meet next.