basic singly-linked list in rust

Question

I'm new to rust and tried to implement a singly-linked list as exercise.

Is this code so far suitable to solve the problem? What elements of the language should I consider to make the code more elegant?

#![allow(dead_code)]
use std::{
 fmt::{Debug, Display},
 ops::Index,
};
struct List {
 value: u8,
 next: Option<Box<List>>,
}
impl List {
 fn new(value: u8) -> Self {
 let next = None;
 Self { value, next }
 }
 fn append(&mut self, value: u8) {
 let new = List::new(value);
 let last = self.get_last_element_mut();
 last.next = Some(Box::new(new));
 }
 fn get_last_element_mut(&mut self) -> &mut Self {
 if self.next.is_none() {
 self
 } else {
 self.next.as_mut().unwrap().get_last_element_mut()
 }
 }
 fn get_last_element(&self) -> &Self {
 if self.next.is_none() {
 self
 } else {
 self.next.as_ref().unwrap().get_last_element()
 }
 }
 fn len(&self) -> usize {
 if self.next.is_none() {
 1
 } else {
 1 + self.next.as_ref().unwrap().len()
 }
 }
 fn get_mut(&mut self, index: usize) -> &mut Self {
 if index == 0 {
 self
 } else {
 self.next.as_mut().unwrap().get_mut(index - 1)
 }
 }
}
impl Index<usize> for List {
 type Output = List;
 fn index(&self, index: usize) -> &Self::Output {
 if index == 0 {
 self
 } else {
 &self
 .next
 .as_ref()
 .expect("line should have {index} more elements")[index - 1]
 }
 }
}
impl PartialEq for List {
 fn eq(&self, other: &Self) -> bool {
 self.value == other.value && self.next == other.next
 }
}
impl Display for List {
 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
 if self.next.is_none() {
 f.write_fmt(format_args!("{}", self.value))
 } else {
 f.write_fmt(format_args!("{} -> ", self.value))?;
 std::fmt::Display::fmt(&self.next.as_ref().unwrap(), f)
 }
 }
}
impl Debug for List {
 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
 f.debug_struct("List")
 .field("value", &self.value)
 .field("next", &self.next)
 .finish()
 }
}
impl From<Vec<u8>> for List {
 fn from(vec: Vec<u8>) -> Self {
 let mut result = List::new(vec[0]);
 for item in &vec[1..] {
 result.append(*item);
 }
 result
 }
}
fn main() {
 let mut l = List::new(5);
 l.append(8);
 l.append(1);
 println!("{}", l[0]);
 println!("{}", l[1]);
 println!("{}", l[2]);
}
#[cfg(test)]
mod tests {
 use super::List;
 #[test]
 fn append() {
 let mut l = List::new(5);
 assert_eq!(l.len(), 1);
 assert_eq!(l.get_last_element().value, 5);
 l.append(8);
 assert_eq!(l.len(), 2);
 assert_eq!(l.get_last_element().value, 8);
 }
 #[test]
 fn mutable() {
 let mut l = List::new(0);
 l.append(1);
 assert_eq!(l.get_last_element().value, 1);
 assert_eq!(l.len(), 2);
 l.get_last_element_mut().value = 5;
 assert_eq!(l.get_last_element().value, 5);
 assert_eq!(l.len(), 2);
 }
 #[test]
 fn representation() {
 let mut l = List::new(1);
 l.append(2);
 l.append(3);
 let repr = format!("{}", l);
 assert_eq!(repr, "1 -> 2 -> 3");
 }
 #[test]
 #[should_panic]
 fn out_of_bounds() {
 let mut l = List::new(1);
 l.append(2);
 let _ = l[l.len()];
 }
 #[test]
 fn from_vec() {
 let input = vec![0, 3, 2, 1, 4];
 let list = List::from(input);
 let repr = format!("{}", list);
 assert_eq!(repr, "0 -> 3 -> 2 -> 1 -> 4");
 }
}
```

Answer 1

The code is generally well-formatted and readable. Also, kudos for including unit tests since they make it easy for reviewers to tweak and test your code.

#![allow(dead_code)]

The reason why you got dead code warnings is (mostly like) because you did not mark public interfaces as pub. Instead of suppressing the warning, you should mark struct List and its methods as pub.

struct List {
 value: u8,
 next: Option<Box<List>>,
}

We can easily generalize the code to handle non-u8 element types:

struct List<T> {
 value: T,
 next: Option<Box<List<T>>>,
}

fn new(value: u8) -> Self {
 let next = None;
 Self { value, next }
}

A simpler alternative is Self { value, next: None }.

fn get_last_element_mut(&mut self) -> &mut Self {
 if self.next.is_none() {
 self
 } else {
 self.next.as_mut().unwrap().get_last_element_mut()
 }
}

Here, we see the common anti-pattern is_none + unwrap, which appears throughout the code a few times. The latter (in theory) performs a redundant second check for is_none and leaves the impression that a panic is possible. The way to go here is to use a match directly:

fn get_last_element_mut(&mut self) -> &mut Self {
 match self.next {
 None => self,
 Some(ref mut next) => next.get_last_element_mut(),
 }
}

(It seems that combinators such as map_or cannot be used here since self.next.as_deref_mut().map_or(self, Self::get_last_element_mut) would alias the mutable reference self.)

I would, however, also consider going with an iterative version to prevent unnecessary recursion:

fn get_last_element_mut(&mut self) -> &mut Self {
 let mut last = self;
 while let Some(ref mut next) = last.next {
 last = next;
 }
 last
}

impl Index<usize> for List {
 type Output = List;
 // ...
}

I would expect type Output = usize (or type Output = T for a generic List<T>) along with an implementation of IndexMut<usize> for consistency with other containers. I would rename the operation you implemented (get_node?) and perhaps make it return an Option instead of panicking.

.expect("line should have {index} more elements")

The panic message is literally "line should have {index} more elements" — no substitution is performed for {index}, which is probably not intended. (In fact, such implicit named arguments only work within the formatting macros format!, print!, write!, etc.). The fix is

.unwrap_or_else(|| panic!("line should have {index} more elements"))

By the way, this is a clever panic message as it mentions the quantity index - len, which conveniently stays constant during the recursion. The standard message is index out of bounds: the len is {} but the index is {}, for comparison, which I personally find more informative.

impl PartialEq for List {
 fn eq(&self, other: &Self) -> bool {
 self.value == other.value && self.next == other.next
 }
}

This is equivalent to the default implementation of PartialEq, which (along with a few other default trait implementations) can be applied using derive when defining struct List:

#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct List {
 // ...
}

impl Display for List {
 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
 if self.next.is_none() {
 f.write_fmt(format_args!("{}", self.value))
 } else {
 f.write_fmt(format_args!("{} -> ", self.value))?;
 std::fmt::Display::fmt(&self.next.as_ref().unwrap(), f)
 }
 }
}

The same is_none + unwrap anti-pattern is present here.

f.write_fmt(format_args!("{}", self.value)) should be

write!(f, "{}", self.value)

Also, fully qualifying std::fmt::Display is not necessary.

For comparison, the containers in the standard library do not implement Display, since there is no one true format suitable for user-facing display. Better would be to support iterators and enable customizable formatters such as itertools::format.

impl From<Vec<u8>> for List {
 fn from(vec: Vec<u8>) -> Self {
 let mut result = List::new(vec[0]);
 for item in &vec[1..] {
 result.append(*item);
 }
 result
 }
}

The usual interface for such conversions is collect, which uses the FromIterator trait. By implementing FromIterator, all kinds of iterators are supported, not just Vec:

impl FromIterator<u8> for List {
 fn from_iter<I>(iter: I) -> Self
 where
 I: IntoIterator<Item = u8>,
 {
 let mut iter = iter.into_iter();
 let mut list = List::new(iter.next().expect("empty lists are not supported"));
 for item in iter {
 list.append(item);
 }
 list
 }
}
// ...
let list = List::from_iter([3, 1, 4, 1, 5, 9]);