Use `Box<T>` when one value needs to live on the heap. `Box::new(value)` allocates it, and the box handles its deallocation. For a list of items, prefer `Vec<T>`; `Box` is the simpler choice for a single item. Unlike `Rc` or `Arc`, it does not provide shared ownership. section 5.5 section 5.10
An optional boxed link
A singly linked node can store its successor as `Option<Box<Node<T>>>`: ```rust struct Node<T> { data: Box<T>, next: Option<Box<Node<T>>>, } impl<T> Node<T> { fn new(data: T) -> Self { Self { data: Box::new(data), next: None } } } ``` `None` marks the end of the chain. Use `Option<Box<T>>` whenever the boxed value might be absent: a `Box` itself is not normally empty. section 5.5
Listing 5.5 Code for a basic, singly linked list in Rust
struct ListItem<T> {
data: Box<T>, #1
next: Option<Box<ListItem<T>>>, #2
}
struct SinglyLinkedList<T> {
head: ListItem<T>, #3
}
impl<T> ListItem<T> {
fn new(data: T) -> Self {
ListItem {
data: Box::new(data), #4
next: None, #5
}
}
fn next(&self) -> Option<&Self> { #6
if let Some(next) = &self.next { #7
Some(next.as_ref()) #8
} else {
None
}
}
fn mut_tail(&mut self) -> &mut Self {
if self.next.is_some() { #9
self.next.as_mut().unwrap().mut_tail() #10
} else {
self #11
}
}
fn data(&self) -> &T {
self.data.as_ref() #12
}
}
impl<T> SinglyLinkedList<T> {
fn new(data: T) -> Self {
SinglyLinkedList {
head: ListItem::new(data), #13
}
}
fn append(&mut self, data: T) {
let mut tail = self.head.mut_tail(); #14
tail.next = Some(Box::new(ListItem::new(data))); #15
}
fn head(&self) -> &ListItem<T> {
&self.head #16
}
}
Inspect the full linked-list implementation for construction and traversal of boxed successor nodes. section 5.5
If a vector raises concerns about allocating a large contiguous region, `Vec<Box<T>>` is an available alternative; do not assume it improves performance without a reason to use it. Heap allocation can also fail, and how to handle that depends on the application and operating system. section 4.3.3 section 5.5
