A simple linked list implemented in Rust
#[derive(Debug)] | |
pub struct LinkedList { | |
head: Option<Box<Node>>, | |
tail: Option<*mut Node>, | |
} | |
#[derive(Debug)] | |
struct Node { | |
value: i32, | |
next: Option<Box<Node>>, | |
} | |
impl LinkedList { | |
pub fn new() -> Self { | |
LinkedList { | |
head: None, | |
tail: None, | |
} | |
} | |
pub fn add_to_tail(&mut self, value: i32) { | |
let mut new_tail = Box::new(Node { value, next: None }); | |
let raw_tail: *mut _ = &mut *new_tail; | |
if self.tail.is_some() { | |
unsafe { (*self.tail.unwrap()).next = Some(new_tail) }; | |
} else { | |
self.head = Some(new_tail); | |
} | |
self.tail = Some(raw_tail); | |
} | |
pub fn remove_head(&mut self) -> Option<i32> { | |
if let Some(head) = &mut self.head { | |
let old_value = Some(head.value); | |
let new_head = head.next.take(); | |
if new_head.is_none() { | |
self.tail = None; | |
}; | |
self.head = new_head; | |
old_value | |
} else { | |
None | |
} | |
} | |
pub fn contains(&mut self, target: i32) -> bool { | |
let mut node = &self.head; | |
while let Some(old_node) = node { | |
match &mut node { | |
Some(node) if node.value == target => return true, | |
_ => (), | |
} | |
node = &old_node.next; | |
} | |
false | |
} | |
} | |
fn main() { | |
let mut list = LinkedList::new(); | |
for i in 0..250_000 { | |
list.add_to_tail(i); | |
} | |
println!("{:?}", list.contains(200_000)); | |
} | |
#[cfg(test)] | |
mod test { | |
use super::LinkedList; | |
#[test] | |
fn tests() { | |
let mut list = LinkedList::new(); | |
assert!(list.tail.is_none()); | |
assert!(list.head.is_none()); | |
list.add_to_tail(4); | |
list.add_to_tail(5); | |
assert_eq!(list.head.as_mut().unwrap().value, 4); | |
assert_eq!(list.contains(5), true); | |
assert_eq!(list.contains(6), false); | |
assert_eq!(list.remove_head(), Some(4)); | |
unsafe { assert_eq!((*list.tail.unwrap()).value, 5) }; | |
assert_eq!(list.remove_head(), Some(5)); | |
assert_eq!(list.remove_head(), None); | |
assert!(list.head.is_none()); | |
assert!(list.tail.is_none()); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This comment has been minimized.
update: https://gist.github.com/AaronM04/0699dd662e64a58332d0955d27a1210f