Reversal of a singly-linked list in Rust

Question

I was trying to write some simple data structures to practice ownership concepts in Rust:

type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
 elem: T,
 next: Link<T>,
}
struct List<T> {
 head: Link<T>,
}
pub struct Iter<'a, T: 'a> {
 next: Option<&'a Node<T>>,
}
impl<T> List<T> {
 pub fn new() -> Self {
 List { head: None }
 }
 pub fn push_front(&mut self, elem: T) {
 let new_node = Box::new(Node {
 elem: elem,
 next: self.head.take(),
 });
 self.head = Some(new_node);
 }
 pub fn reverse(&mut self) {
 if self.head.is_none() || self.head.as_ref().unwrap().next.is_none() {
 return;
 }
 let mut prev = None;
 let mut current_node = self.head.take();
 while current_node.is_some() {
 let next = current_node.as_mut().unwrap().next.take();
 current_node.as_mut().unwrap().next = prev.take();
 prev = current_node.take();
 current_node = next;
 }
 self.head = prev.take();
 }
 pub fn iter(&self) -> Iter<T> {
 Iter { next: self.head.as_ref().map(|node| &**node) }
 }
}
impl<'a, T> Iterator for Iter<'a, T> {
 type Item = &'a T;
 fn next(&mut self) -> Option<Self::Item> {
 self.next.map(|node| {
 self.next = node.next.as_ref().map(|node| &**node);
 &node.elem
 })
 }
}
fn main() {
 let mut l = List::new();
 l.push_front(3);
 l.push_front(2);
 l.push_front(1);
 l.push_front(12);
 for item in l.iter() {
 print!("{} ", item);
 }
 println!();
 l.reverse();
 for item in l.iter() {
 print!("{} ", item);
 }
 println!();
}

Link to Rust Playground

Answer 1

Before I begin, I recommend reading Learning Rust With Entirely Too Many Linked Lists.

1. Avoid unwraps, especially those after checking is_some. Use pattern matching instead.

2. The first test in reverse is redundant with the rest of the logic.

3. Implement Debug or Display to DRY up the printing of the list.

4. You should have some tests, especially for edge cases: 0, 1, and 2 items.

5. I'm not a fan of side effects inside of a map - it should err more on the side of purely functional. I'd use a match, even though it's more lines of code.

6. I'd simplify the iterator by just keeping a &Link

7. You could choose to remove the temporary variable from push_front.

8. for item in foo.iter() is usually written as for item in &foo, which implies that you need to implement IntoIterator for a reference to your type.

use std::fmt;
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
 elem: T,
 next: Link<T>,
}
struct List<T> {
 head: Link<T>,
}
pub struct Iter<'a, T: 'a> {
 next: &'a Link<T>,
}
impl<T> List<T> {
 pub fn new() -> Self {
 List { head: None }
 }
 pub fn push_front(&mut self, elem: T) {
 self.head = Some(Box::new(Node {
 elem: elem,
 next: self.head.take(),
 }));
 }
 pub fn reverse(&mut self) {
 let mut prev = None;
 let mut current_node = self.head.take();
 while let Some(mut current_node_inner) = current_node.take() {
 let next = current_node_inner.next.take();
 current_node_inner.next = prev.take();
 prev = Some(current_node_inner);
 current_node = next;
 }
 self.head = prev.take();
 }
 pub fn iter(&self) -> Iter<T> {
 Iter { next: &self.head }
 }
}
impl<'a, T> IntoIterator for &'a List<T> {
 type Item = &'a T;
 type IntoIter = Iter<'a, T>;
 fn into_iter(self) -> Self::IntoIter {
 self.iter()
 }
}
impl<'a, T> Iterator for Iter<'a, T> {
 type Item = &'a T;
 fn next(&mut self) -> Option<Self::Item> {
 match self.next.as_ref() {
 Some(next) => {
 self.next = &next.next;
 Some(&next.elem)
 }
 None => None,
 }
 }
}
impl<T> fmt::Debug for List<T>
 where T: fmt::Debug,
{
 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 for item in self {
 write!(f, "{:?} ", item)?;
 }
 Ok(())
 }
}

• Anurag Soni: Thanks for a thorough reply!! It is definitely much nicer to use pattern matching instead of all the unwraps. It had completely skipped my mind :)