Project 2: A Linked List From Scratch

A functional singly linked list, with methods for push, pop, and iterating over the elements.

Quick Reference

Attribute Value
Primary Language Rust
Alternative Languages C, C++
Difficulty Level 3: Advanced
Time Estimate 1-2 weeks
Knowledge Area Data Structures / Memory Management
Tooling cargo
Prerequisites Project 1, a firm grasp of basic structs and enums.

What You Will Build

A functional singly linked list, with methods for push, pop, and iterating over the elements.

Why It Matters

This project builds core skills that appear repeatedly in real-world systems and tooling.

Core Challenges

  • Defining the Node struct → maps to using Box<T> to prevent infinite type recursion
  • Implementing push and pop → maps to transferring ownership of nodes
  • Handling the head pointer → maps to using Option<T> to represent a possibly empty list
  • Trying to implement an iterator → maps to fighting the borrow checker over mutable and immutable references

Key Concepts

  • Ownership: “The Rust Programming Language” Ch. 4
  • Smart Pointers (Box): “The Rust Programming Language” Ch. 15
  • Option<T>: “The Rust Programming Language” Ch. 6
  • Recursive Data Structures: “Too Many Linked Lists” (This entire tutorial is dedicated to this problem).

Real-World Outcome

// In your tests
let mut list = List::new();
list.push(1);
list.push(2);
list.push(3);

assert_eq!(list.pop(), Some(3));
assert_eq!(list.pop(), Some(2));

list.push(4);
assert_eq!(list.pop(), Some(4));
assert_eq!(list.pop(), Some(1));
assert_eq!(list.pop(), None);

Implementation Guide

  1. Reproduce the simplest happy-path scenario.
  2. Build the smallest working version of the core feature.
  3. Add input validation and error handling.
  4. Add instrumentation/logging to confirm behavior.
  5. Refactor into clean modules with tests.

Milestones

  • Milestone 1: Minimal working program that runs end-to-end.
  • Milestone 2: Correct outputs for typical inputs.
  • Milestone 3: Robust handling of edge cases.
  • Milestone 4: Clean structure and documented usage.

Validation Checklist

  • Output matches the real-world outcome example
  • Handles invalid inputs safely
  • Provides clear errors and exit codes
  • Repeatable results across runs

References

  • Main guide: LEARN_RUST_FROM_FIRST_PRINCIPLES.md
  • “Too Many Linked Lists” by Alexis Beingessner