Created
October 2, 2020 20:27
-
-
Save AnthonyMikh/f9ece0aae6b042fbf440ac2550908f0a to your computer and use it in GitHub Desktop.
Totally safe singly linked list in Rust
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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