Skip to content

Instantly share code, notes, and snippets.

@AaronM04
Forked from codesections/linked_list.rs
Last active March 2, 2020 03:38
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save AaronM04/0699dd662e64a58332d0955d27a1210f to your computer and use it in GitHub Desktop.
Save AaronM04/0699dd662e64a58332d0955d27a1210f 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
}
}
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());
}
}
@AaronM04
Copy link
Author

AaronM04 commented Jan 7, 2019

Updated to include the fix from Sergey Bugaev, wrapped in an impl Drop.

@vcfxb
Copy link

vcfxb commented Jan 9, 2019

The use of unsafe makes this somewhat unidiomatic. Could I take a stab at making some edits to make it more idiomatic?

@AaronM04
Copy link
Author

Sure, go ahead! (sorry for the late reply)

@iGetSchwifty
Copy link

iGetSchwifty commented Mar 2, 2020

Would lifetimes be a way to make it more idiomatic? Not sure how that would look as I tried my newbie hand at it and couldnt get the lifetime solution to properly compile. This *mut/unsafe is ultimately what I used to get the LinkedList to work properly for my own playground project.

@AaronM04
Copy link
Author

AaronM04 commented Mar 2, 2020

Would lifetimes be a way to make it more idiomatic?

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.

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