Skip to content

Instantly share code, notes, and snippets.

@codesections
Created January 6, 2019 23:02
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 3 You must be signed in to fork a gist
  • Save codesections/bef7f95973ea5bb2d0046ab99270928b to your computer and use it in GitHub Desktop.
Save codesections/bef7f95973ea5bb2d0046ab99270928b to your computer and use it in GitHub Desktop.
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());
}
}
@AaronM04
Copy link

AaronM04 commented Jan 7, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment