1034 Intermediate

1034-linked-list-safe — Safe Linked List

Functional Programming

Tutorial

The Problem

Linked lists are a foundational data structure in functional programming — OCaml's list type is a linked list at the machine level. In Rust, implementing a linked list in safe code is notoriously tricky because the borrow checker must verify that no two nodes share ownership. The canonical safe approach uses Option<Box<Node<T>>> for the next pointer, which gives single ownership through the Box and None for the terminator.

This example demonstrates why Rust linked lists require more thought than in garbage-collected languages, and how Option<Box<Node<T>>> cleanly solves the ownership problem.

🎯 Learning Outcomes

• Implement a singly-linked list using Option<Box<Node<T>>> in safe Rust

• Understand why Box<T> is needed to break the recursive size computation

• Use .take() for efficient ownership transfer from Option<Box<_>>

• Implement push, pop, peek, and iteration

• Know when to use std::collections::LinkedList vs Vec in production

Code Example

#![allow(clippy::all)]
// 1034: Safe Linked List — Option<Box<Node<T>>>
// Building a singly-linked list using only safe Rust

/// A singly-linked list node
#[derive(Debug)]
struct Node<T> {
    value: T,
    next: Option<Box<Node<T>>>,
}

/// A singly-linked list (stack-like: push/pop at head)
#[derive(Debug)]
struct List<T> {
    head: Option<Box<Node<T>>>,
    len: usize,
}

impl<T> List<T> {
    fn new() -> Self {
        List { head: None, len: 0 }
    }

    fn push(&mut self, value: T) {
        let new_node = Box::new(Node {
            value,
            next: self.head.take(), // Take ownership of old head
        });
        self.head = Some(new_node);
        self.len += 1;
    }

    fn pop(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            self.head = node.next;
            self.len -= 1;
            node.value
        })
    }

    fn peek(&self) -> Option<&T> {
        self.head.as_ref().map(|node| &node.value)
    }

    fn len(&self) -> usize {
        self.len
    }

    fn is_empty(&self) -> bool {
        self.head.is_none()
    }

    fn iter(&self) -> ListIter<T> {
        ListIter {
            current: self.head.as_deref(),
        }
    }
}

/// Iterator over list references
struct ListIter<'a, T> {
    current: Option<&'a Node<T>>,
}

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

    fn next(&mut self) -> Option<Self::Item> {
        self.current.map(|node| {
            self.current = node.next.as_deref();
            &node.value
        })
    }
}

/// Implement Drop to avoid stack overflow on large lists
impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut current = self.head.take();
        while let Some(mut node) = current {
            current = node.next.take();
        }
    }
}

fn basic_operations() {
    let mut list = List::new();
    assert!(list.is_empty());

    list.push(1);
    list.push(2);
    list.push(3);
    assert_eq!(list.len(), 3);
    assert_eq!(list.peek(), Some(&3));

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

fn iterator_demo() {
    let mut list = List::new();
    for i in (1..=5).rev() {
        list.push(i);
    }

    let collected: Vec<_> = list.iter().copied().collect();
    assert_eq!(collected, vec![1, 2, 3, 4, 5]);

    let sum: i32 = list.iter().sum();
    assert_eq!(sum, 15);

    let evens: Vec<_> = list.iter().filter(|&&x| x % 2 == 0).copied().collect();
    assert_eq!(evens, vec![2, 4]);
}

fn from_vec() {
    let mut list = List::new();
    for &x in [5, 4, 3, 2, 1].iter() {
        list.push(x);
    }
    let items: Vec<_> = list.iter().copied().collect();
    assert_eq!(items, vec![1, 2, 3, 4, 5]);
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_basic() {
        basic_operations();
    }

    #[test]
    fn test_iterator() {
        iterator_demo();
    }

    #[test]
    fn test_from_vec() {
        from_vec();
    }

    #[test]
    fn test_empty() {
        let list: List<i32> = List::new();
        assert!(list.is_empty());
        assert_eq!(list.peek(), None);
        assert_eq!(list.len(), 0);
    }

    #[test]
    fn test_single_element() {
        let mut list = List::new();
        list.push(42);
        assert_eq!(list.peek(), Some(&42));
        assert_eq!(list.pop(), Some(42));
        assert!(list.is_empty());
    }
}

(* 1034: Safe Linked List *)
(* OCaml lists ARE linked lists — this is the native data structure *)

(* Approach 1: OCaml's built-in list (singly-linked, immutable) *)
let builtin_list () =
  let lst = [1; 2; 3] in
  (* Cons is O(1) *)
  let lst = 0 :: lst in
  assert (lst = [0; 1; 2; 3]);
  (* Pattern match for head/tail *)
  let (hd, tl) = match lst with
    | x :: xs -> (x, xs)
    | [] -> failwith "empty"
  in
  assert (hd = 0);
  assert (tl = [1; 2; 3])

(* Approach 2: Custom linked list type (explicit) *)
type 'a node = Nil | Cons of 'a * 'a node

let rec to_list = function
  | Nil -> []
  | Cons (x, next) -> x :: to_list next

let rec from_list = function
  | [] -> Nil
  | x :: xs -> Cons (x, from_list xs)

let rec length = function
  | Nil -> 0
  | Cons (_, next) -> 1 + length next

let push x lst = Cons (x, lst)

let pop = function
  | Nil -> None
  | Cons (x, next) -> Some (x, next)

let custom_list () =
  let lst = from_list [1; 2; 3] in
  assert (length lst = 3);
  let lst = push 0 lst in
  assert (length lst = 4);
  let (v, lst) = Option.get (pop lst) in
  assert (v = 0);
  assert (to_list lst = [1; 2; 3])

(* Approach 3: Functional operations on custom list *)
let rec map f = function
  | Nil -> Nil
  | Cons (x, next) -> Cons (f x, map f next)

let rec filter p = function
  | Nil -> Nil
  | Cons (x, next) ->
    if p x then Cons (x, filter p next)
    else filter p next

let rec fold f acc = function
  | Nil -> acc
  | Cons (x, next) -> fold f (f acc x) next

let functional_ops () =
  let lst = from_list [1; 2; 3; 4; 5] in
  let doubled = map (fun x -> x * 2) lst in
  assert (to_list doubled = [2; 4; 6; 8; 10]);
  let evens = filter (fun x -> x mod 2 = 0) lst in
  assert (to_list evens = [2; 4]);
  let sum = fold (fun acc x -> acc + x) 0 lst in
  assert (sum = 15)

let () =
  builtin_list ();
  custom_list ();
  functional_ops ();
  Printf.printf "✓ All tests passed\n"

Key Differences

Ownership: Rust's Box<Node> enforces single ownership; OCaml nodes can be shared (immutable structural sharing via GC).

Mutability: Rust's list is mutable (push/pop in place); OCaml's lists are immutable (prepend creates new node, old list unchanged).

Safety without GC: Rust's Option<Box<Node>> is safe Rust with no garbage collector; OCaml's GC handles the memory automatically.

**std::collections::LinkedList**: Rust's stdlib doubly-linked list is rarely recommended; Vec is almost always better due to cache locality.

OCaml Approach

OCaml's built-in list 'a list is a singly-linked list with structural sharing:

(* OCaml's list IS a linked list at the machine level *)
type 'a list = [] | (::) of 'a * 'a list

let push value lst = value :: lst
let pop = function [] -> None | x :: rest -> Some (x, rest)

OCaml lists are immutable and use GC-managed shared nodes. Appending to the front is O(1); appending to the back is O(n). Both languages agree on the O(1) prepend for linked lists.

Full Source

#![allow(clippy::all)]
// 1034: Safe Linked List — Option<Box<Node<T>>>
// Building a singly-linked list using only safe Rust

/// A singly-linked list node
#[derive(Debug)]
struct Node<T> {
    value: T,
    next: Option<Box<Node<T>>>,
}

/// A singly-linked list (stack-like: push/pop at head)
#[derive(Debug)]
struct List<T> {
    head: Option<Box<Node<T>>>,
    len: usize,
}

impl<T> List<T> {
    fn new() -> Self {
        List { head: None, len: 0 }
    }

    fn push(&mut self, value: T) {
        let new_node = Box::new(Node {
            value,
            next: self.head.take(), // Take ownership of old head
        });
        self.head = Some(new_node);
        self.len += 1;
    }

    fn pop(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            self.head = node.next;
            self.len -= 1;
            node.value
        })
    }

    fn peek(&self) -> Option<&T> {
        self.head.as_ref().map(|node| &node.value)
    }

    fn len(&self) -> usize {
        self.len
    }

    fn is_empty(&self) -> bool {
        self.head.is_none()
    }

    fn iter(&self) -> ListIter<T> {
        ListIter {
            current: self.head.as_deref(),
        }
    }
}

/// Iterator over list references
struct ListIter<'a, T> {
    current: Option<&'a Node<T>>,
}

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

    fn next(&mut self) -> Option<Self::Item> {
        self.current.map(|node| {
            self.current = node.next.as_deref();
            &node.value
        })
    }
}

/// Implement Drop to avoid stack overflow on large lists
impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut current = self.head.take();
        while let Some(mut node) = current {
            current = node.next.take();
        }
    }
}

fn basic_operations() {
    let mut list = List::new();
    assert!(list.is_empty());

    list.push(1);
    list.push(2);
    list.push(3);
    assert_eq!(list.len(), 3);
    assert_eq!(list.peek(), Some(&3));

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

fn iterator_demo() {
    let mut list = List::new();
    for i in (1..=5).rev() {
        list.push(i);
    }

    let collected: Vec<_> = list.iter().copied().collect();
    assert_eq!(collected, vec![1, 2, 3, 4, 5]);

    let sum: i32 = list.iter().sum();
    assert_eq!(sum, 15);

    let evens: Vec<_> = list.iter().filter(|&&x| x % 2 == 0).copied().collect();
    assert_eq!(evens, vec![2, 4]);
}

fn from_vec() {
    let mut list = List::new();
    for &x in [5, 4, 3, 2, 1].iter() {
        list.push(x);
    }
    let items: Vec<_> = list.iter().copied().collect();
    assert_eq!(items, vec![1, 2, 3, 4, 5]);
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_basic() {
        basic_operations();
    }

    #[test]
    fn test_iterator() {
        iterator_demo();
    }

    #[test]
    fn test_from_vec() {
        from_vec();
    }

    #[test]
    fn test_empty() {
        let list: List<i32> = List::new();
        assert!(list.is_empty());
        assert_eq!(list.peek(), None);
        assert_eq!(list.len(), 0);
    }

    #[test]
    fn test_single_element() {
        let mut list = List::new();
        list.push(42);
        assert_eq!(list.peek(), Some(&42));
        assert_eq!(list.pop(), Some(42));
        assert!(list.is_empty());
    }
}

(* 1034: Safe Linked List *)
(* OCaml lists ARE linked lists — this is the native data structure *)

(* Approach 1: OCaml's built-in list (singly-linked, immutable) *)
let builtin_list () =
  let lst = [1; 2; 3] in
  (* Cons is O(1) *)
  let lst = 0 :: lst in
  assert (lst = [0; 1; 2; 3]);
  (* Pattern match for head/tail *)
  let (hd, tl) = match lst with
    | x :: xs -> (x, xs)
    | [] -> failwith "empty"
  in
  assert (hd = 0);
  assert (tl = [1; 2; 3])

(* Approach 2: Custom linked list type (explicit) *)
type 'a node = Nil | Cons of 'a * 'a node

let rec to_list = function
  | Nil -> []
  | Cons (x, next) -> x :: to_list next

let rec from_list = function
  | [] -> Nil
  | x :: xs -> Cons (x, from_list xs)

let rec length = function
  | Nil -> 0
  | Cons (_, next) -> 1 + length next

let push x lst = Cons (x, lst)

let pop = function
  | Nil -> None
  | Cons (x, next) -> Some (x, next)

let custom_list () =
  let lst = from_list [1; 2; 3] in
  assert (length lst = 3);
  let lst = push 0 lst in
  assert (length lst = 4);
  let (v, lst) = Option.get (pop lst) in
  assert (v = 0);
  assert (to_list lst = [1; 2; 3])

(* Approach 3: Functional operations on custom list *)
let rec map f = function
  | Nil -> Nil
  | Cons (x, next) -> Cons (f x, map f next)

let rec filter p = function
  | Nil -> Nil
  | Cons (x, next) ->
    if p x then Cons (x, filter p next)
    else filter p next

let rec fold f acc = function
  | Nil -> acc
  | Cons (x, next) -> fold f (f acc x) next

let functional_ops () =
  let lst = from_list [1; 2; 3; 4; 5] in
  let doubled = map (fun x -> x * 2) lst in
  assert (to_list doubled = [2; 4; 6; 8; 10]);
  let evens = filter (fun x -> x mod 2 = 0) lst in
  assert (to_list evens = [2; 4]);
  let sum = fold (fun acc x -> acc + x) 0 lst in
  assert (sum = 15)

let () =
  builtin_list ();
  custom_list ();
  functional_ops ();
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_basic() {
        basic_operations();
    }

    #[test]
    fn test_iterator() {
        iterator_demo();
    }

    #[test]
    fn test_from_vec() {
        from_vec();
    }

    #[test]
    fn test_empty() {
        let list: List<i32> = List::new();
        assert!(list.is_empty());
        assert_eq!(list.peek(), None);
        assert_eq!(list.len(), 0);
    }

    #[test]
    fn test_single_element() {
        let mut list = List::new();
        list.push(42);
        assert_eq!(list.peek(), Some(&42));
        assert_eq!(list.pop(), Some(42));
        assert!(list.is_empty());
    }
}

Deep Comparison

Safe Linked List — Comparison

Core Insight

OCaml's list IS a linked list — it's the default, most natural data structure. In Rust, linked lists fight the ownership system. Option<Box<Node<T>>> works for singly-linked lists but requires careful use of take() to move ownership. This is a key lesson in why Rust prefers Vec.

OCaml Approach

• Lists are built-in: [1; 2; 3] is a linked list

• Immutable cons cells: x :: xs creates a new head

• Pattern matching for destructuring

• GC handles memory — no ownership concerns

• Custom ADT: type 'a node = Nil | Cons of 'a * 'a node

Rust Approach

• Option<Box<Node<T>>> — Box for heap allocation, Option for null

• take() on Option to transfer ownership (replaces with None)

• Must implement Drop manually to avoid stack overflow on large lists

• Iterator requires lifetime-annotated struct

• No shared tails (unlike OCaml's persistent lists)

Comparison Table

Feature	OCaml	Rust (safe)
Built-in	Yes (`list`)	No (must build)
Mutability	Immutable	Mutable
Memory management	GC	Ownership + Box
Shared tails	Yes (free)	No (would need Rc)
Push front	`x :: xs`	`self.head.take()` dance
Pattern match	Native	`if let` / `match`
Drop behavior	GC	Must implement iterative Drop
Recommended	Always	Rarely — use `Vec` instead

Exercises

Add a reverse(&mut self) method that reverses the list in place by relinking nodes.

Implement IntoIterator for List<T> so you can use it in for loops.

Write a merge_sorted(a: List<i32>, b: List<i32>) -> List<i32> function that merges two sorted lists into a new sorted list.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust