Linked List in Safe Rust

Why the Borrow Checker Hates Linked Lists

A node wants to point at the next node, but only one owner may exist. That tension is the subject of "Too Many Linked Lists": std::collections::LinkedList uses unsafe internally because safe singly-linked lists fight the type system.

rustCopy
Loading…

• Box gives heap indirection with a known size, enabling recursive enums
• Rc + RefCell enables shared mutable graphs at runtime borrow cost
• Push/pop need &mut self because you mutate head pointers

Patterns You Will Hit

• "cannot move out of borrowed content" when iterating and mutating
• "borrowed value does not live long enough" when returning interior references
• Fixing with Option<Box<Node>> ownership instead of raw links

For this exercise, you will implement push, pop, and iterate on a safe singly-linked list. This task asks you to read compiler errors as design feedback, because choosing Vec over LinkedList in production is often a cache decision, but building the list teaches ownership better than any slide deck.

Keep the relevant man page, ABI doc, or Rust reference chapter open while you work. When your output disagrees with the reference implementation on the same machine, the mismatch is usually an alignment rule, an off-by-one terminator, or a register slot you misread in GDB.