Skip to content

Instantly share code, notes, and snippets.

@alexkehayias
Created November 19, 2016 23:24
Show Gist options
  • Save alexkehayias/ce802007770cb9eff86e03169ad88ccf to your computer and use it in GitHub Desktop.
Save alexkehayias/ce802007770cb9eff86e03169ad88ccf to your computer and use it in GitHub Desktop.
Generic linked list in Rust
use std::fmt;
enum LinkedList<T> {
// Can't have a recursive type declaration here because there is no way
// to size it. So we put it on the Heap by using a Box and now we can
// have a recursive type.
Pair(T, Box<LinkedList<T>>),
Nil,
}
impl<T> LinkedList<T> {
pub fn new () -> LinkedList<T> {
LinkedList::Nil
}
fn push(self, val: T) -> Self {
LinkedList::Pair(val, Box::new(self))
}
fn pop(self) -> Option<T> {
match self {
LinkedList::Pair(head, _) => Some(head),
LinkedList::Nil => None,
}
}
fn drop(self) -> Self {
match self {
LinkedList::Pair(_, tail) => *tail,
LinkedList::Nil => self,
}
}
}
impl<T> fmt::Display for LinkedList<T> where
T: std::fmt::Display {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "[ ");
let mut node = self;
while let LinkedList::Pair(ref head, ref tail) = *node {
write!(f, "{} ", head);
node = tail;
}
write!(f, "]")
}
}
fn main () {
let mut x = LinkedList::<i32>::new();
println!("My very simple linked list: {}", x);
x = x.push(1).push(2).push(3).push(4);
println!("You can push: {}", x);
x = x.drop();
println!("You can drop: {}", x);
let y = x.pop();
println!("You can pop: {:?}", y);
}
@alexkehayias
Copy link
Author

Here's a pretty naive implementation of a generic, immutable, linked list in Rust based on http://rustbyexample.com/custom_types/enum/testcase_linked_list.html

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