Skip to content

Instantly share code, notes, and snippets.

@longshorej
Created January 24, 2019 00:37
Show Gist options
  • Save longshorej/1362b87c4e911024bbbfac9a26c7056d to your computer and use it in GitHub Desktop.
Save longshorej/1362b87c4e911024bbbfac9a26c7056d to your computer and use it in GitHub Desktop.
Rust singly linked list
use std::mem;
pub enum ListNode<A> {
Cons(A, Box<ListNode<A>>),
Nil
}
/// A List is a singly-linked list that allows items to be
/// prepended.
///
/// Once constructed, a list can be consumed by calling
/// into_iter.
pub struct List<A> {
entry: ListNode<A>
}
impl<A> List<A> {
/// Construct a new (empty) list.
pub fn new() -> Self {
Self { entry: ListNode::Nil }
}
/// Prepend the supplied item onto the list.
pub fn prepend(&mut self, item: A) {
let mut current_entry = ListNode::Nil;
mem::swap(&mut self.entry, &mut current_entry);
self.entry = ListNode::Cons(item, Box::new(current_entry));
}
}
pub struct ListIterator<A> {
entry: ListNode<A>
}
impl<A> Iterator for ListIterator<A> {
type Item = A;
fn next(&mut self) -> Option<A> {
let mut current_list = ListNode::Nil;
mem::swap(&mut self.entry, &mut current_list);
match current_list {
ListNode::Cons(e, rest) => {
self.entry = *rest;
Some(e)
}
ListNode::Nil => {
None
}
}
}
}
impl<A> IntoIterator for List<A> {
type Item = A;
type IntoIter = ListIterator<A>;
fn into_iter(self) -> Self::IntoIter {
ListIterator {
entry: self.entry
}
}
}
#[test]
fn test_list_empty() {
let mut list = List::new();
assert!(list.into_iter().collect::<Vec<usize>>().is_empty());
}
#[test]
fn test_list_non_empty() {
let mut list = List::new();
list.prepend(1);
list.prepend(2);
list.prepend(3);
assert_eq!(list.into_iter().collect::<Vec<usize>>(), vec![3, 2, 1]);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment