Language FoundationsRust for Systems ProgrammingHard

Linked List in Safe Rust

Master the fundamental concepts of rust for systems programming through this focused micro-challenge.

~90 minutes Rust for Systems Programming Ready to learn

Topic Overview

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.

rust
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.

Implementation Task

Your Task

Build a singly linked stack in safe Rust: struct Node { v: i32, next: Option<Box<Node>> }, then drive it from stdin commands. Every operation is a lesson in ownership: pop moves the head out with Option::take, peek returns a shared borrow, add goes through peek_mut, reverse relinks boxes without cloning, and remove walks a &mut Option<Box<Node>> cursor.

Input

One command per line (blank lines are ignored). X is a 32-bit signed integer.

c
Loading…

Output

Command	Output
`pop`, `peek`	`Some(V)`, or `None` on an empty list
`add X`	the new front value as `Some(V)`, `None` on an empty list, or `overflow` (value unchanged) if the result does not fit in an i32
`len`	`len=N`
`remove X`	`removed X` or `X not found`
`print`	`[3, 2, 1]` (Debug style, `[]` when empty)
`sum`	`sum=S`

A line with an unknown command or the wrong number of arguments prints unknown command: LINE. An argument that is not a valid i32 prints bad number: TOKEN.

Example

Input:

c
Loading…

Output:

c
Loading…

Requirements

No unsafe, no Rc/RefCell, and no clone() of nodes. Ownership moves through Option<Box<Node>>.
reverse and remove must relink the existing boxes in place.

Hidden tests cover operations on an empty list, removing from the front, middle and end, removing a missing value, i32 overflow in add, i64 sums, and malformed commands.