Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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

This comment has been minimized.

Copy link
Owner Author

commented Jan 7, 2019

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

@Alfriadox

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link
Owner Author

commented Feb 25, 2019

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.