Created
January 6, 2019 23:02
-
-
Save codesections/bef7f95973ea5bb2d0046ab99270928b to your computer and use it in GitHub Desktop.
A simple linked list implemented in Rust
This file contains hidden or 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
#[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
update: https://gist.github.com/AaronM04/0699dd662e64a58332d0955d27a1210f