A singly linked list stores nodes whose links point to at most one successor. In Rust, ownership and Option make the structure safe: it cannot contain null pointers or invalid links. 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
}
}
The implementation uses Box for heap allocation, Option<Box<ListItem<T>>> for the successor, and methods for construction and traversal. section 5.5
Use the example primarily to practice Rust memory management:
- Implement the list from scratch, then study how ownership, borrowing, Box, Option, and pattern matching maintain validity. section 5.5
- Treat the implementation as instructional rather than optimized; prefer Vec for most practical cases, or std::collections::LinkedList when a linked list is required. section 5.5
Traversing the list
Constructing a list with head, middle, and tail values and repeatedly calling next() prints: item: head, item: middle, item: tail.
