Created
January 24, 2019 00:37
-
-
Save longshorej/1362b87c4e911024bbbfac9a26c7056d to your computer and use it in GitHub Desktop.
Rust singly linked list
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
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