Skip to content

Instantly share code, notes, and snippets.

@AnthonyMikh
Created October 2, 2020 20:27
Show Gist options
  • Star 4 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save AnthonyMikh/f9ece0aae6b042fbf440ac2550908f0a to your computer and use it in GitHub Desktop.
Save AnthonyMikh/f9ece0aae6b042fbf440ac2550908f0a to your computer and use it in GitHub Desktop.
Totally safe singly linked list in Rust
struct Node<T> {
item: T,
next: NextNode<T>,
}
type NextNode<T> = Option<Box<Node<T>>>;
impl<T> Node<T> {
fn replace_tail(&mut self, new_tail: NextNode<T>) -> NextNode<T> {
std::mem::replace(&mut self.next, new_tail)
}
}
struct List<T> {
head: Option<Box<Node<T>>>,
}
impl<T> List<T> {
fn new() -> Self {
Self {
head: None
}
}
fn prepend(&mut self, item: T) {
self.head = Some(Box::new(Node {
item,
next: self.head.take(),
}))
}
fn reverse(&mut self) {
let mut acc = self.head.take();
let mut pending = match acc.as_mut() {
Some(acc) => acc.next.take(),
None => return,
};
while let Some(mut old_head) = pending {
pending = old_head.replace_tail(acc);
acc = Some(old_head);
}
self.head = acc;
}
fn iter(&self) -> impl Iterator<Item = &T> + '_ {
let mut current = self.head.as_deref();
std::iter::from_fn(move || {
let ret = current?;
current = ret.next.as_deref();
Some(&ret.item)
})
}
}
// Stricly speaking, it is not necessary, but without this impl
// dropping list can overflow the stack
impl<T> Drop for List<T> {
fn drop(&mut self) {
while let Some(node) = self.head.take() {
self.head = node.next;
}
}
}
use std::fmt::{self, Debug};
impl<T: Debug> Debug for List<T> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_list().entries(self.iter()).finish()
}
}
fn main() {
let mut list = List::new();
list.prepend(4);
list.prepend(3);
list.prepend(2);
list.prepend(1);
println!("{:?}", list);
list.reverse();
println!("{:?}", list);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment