-
-
Save AaronM04/0699dd662e64a58332d0955d27a1210f 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 | |
} | |
} | |
impl Drop for LinkedList { | |
fn drop(&mut self) { | |
let mut node = self.head.take(); | |
while let Some(mut next_node) = node { | |
node = next_node.next.take() | |
} | |
} | |
} | |
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
I'm not sure what that would look like either. If you have no need to add nodes to the tail, then you can remove the unsafe stuff.