A singly linked list is a sequence of nodes, each referring to the next: A → B → C. In Rust, it is a useful example of recursive generics, ownership, and iteration. It is not automatically a better collection than Vec. section 2.1.3 section 10.4
Start with a recursive node
A small node can store `data: Box<T>` and `next: Option<Box<ListItem<T>>>`. `Option` represents either another boxed node or the end of the list. This shows how a generic structure can refer to itself, but it is a teaching example rather than a practical implementation to adopt unchanged. section 2.1.3
#[derive(Clone)] #1
struct ListItem<T>
where
T: Clone,
{
data: Box<T>,
next: Option<Box<ListItem<T>>>,
}
Inspect the boxed value and optional boxed next node in the generic `ListItem<T>` declaration. section 2.1.3
A more developed implementation uses `Rc` and `RefCell` to manage links and shared access. Keep traversal separate from the collection: implementing `Iterator` directly on `LinkedList` is discouraged here. Instead, give the list iterator methods and give each returned iterator its own traversal state. section 3.2.4
The three traversal modes express different relationships to the list:
- `iter(&self)` traverses shared references to items. section 3.2.4
- `iter_mut(&mut self)` traverses mutable references to items. section 3.2.4
- `into_iter(self)` consumes the list and yields items. Implementing `IntoIterator` for the list and its reference forms also enables `for` loops. section 3.2.4
The iterator implementation is not a copy-and-paste recipe: its reference-yielding version uses `unsafe`, while consuming traversal attempts to unwrap shared `Rc` values. If the goal is simply to collect transformed items, Rust’s standard-library `LinkedList` can instead be a `collect()` target; one example parses strings into integers with `flat_map()` before collecting. section 3.2.4 section 3.2.5
Choose a linked list for a demonstrated need, not as a reflexive optimization. In the supplied append, find, and remove benchmarks, `Vec` beats `LinkedList` on every test and uses memory more efficiently. Benchmark the operations that matter to your workload before replacing `Vec`. section 10.4
Listing 10.8 Benchmark results for Vec, HashSet, and LinkedList
running 9 tests test tests::list_append ... bench: 53,860,800 ns/iter (+/- 2,306,429) test tests::list_find ... bench: 527,207 ns/iter (+/- 26,305) test tests::list_remove ... bench: 61,830,454 ns/iter (+/- 1,462,953) test tests::set_append ... bench: 23,774,245 ns/iter (+/- 549,095) test tests::set_find ... bench: 11 ns/iter (+/- 0) test tests::set_remove ... bench: 839,977 ns/iter (+/- 4,571) test tests::vec_append ... bench: 2,095,262 ns/iter (+/- 146,611) test tests::vec_find ... bench: 133,359 ns/iter (+/- 11,424) test tests::vec_remove ... bench: 3,319,558 ns/iter (+/- 57,979) test result: ok. 0 passed; 0 failed; 0 ignored; 9 measured; 0 filtered out; finished in 136.97s
Compare the measured append, find, and remove times; these results are illustrative and can differ by machine. section 10.4
