Skip to content

Instantly share code, notes, and snippets.

@dbyr
Last active January 9, 2020 04:25
Show Gist options
  • Save dbyr/16ec547c5815fa6621ef7b0b6f4fe0f7 to your computer and use it in GitHub Desktop.
Save dbyr/16ec547c5815fa6621ef7b0b6f4fe0f7 to your computer and use it in GitHub Desktop.
My first attempt at implementing a linked list in Rust. The basic structure is based off the linked list found in the "rust by example" instruction docs. I have added some extra methods to make the implementation more complete.
mod linked_list {
use std::fmt::Display;
use std::default::Default;
type Next<V> = Option<Box<Node<V>>>;
struct Node<V> {
val: V,
next: Next<V>,
}
pub struct LList<V> {
head: Next<V>,
size: usize,
}
impl<V> LList<V> where V: Display + Default {
pub fn new() -> LList<V> {
LList{head: None, size: 0}
}
pub fn len(&self) -> usize {
return self.size;
}
pub fn print(&self) {
print!("[");
if let Some(ref n) = self.head {
n.print_order(true);
}
println!("]");
}
pub fn get(&self, i: usize) -> Option<&V> {
if let Some(n) = &self.head {
n.get(i)
} else {
None
}
}
pub fn remove(&mut self, i: usize) -> Option<V> {
if i >= self.size {
None
} else if let Some(mut h) = self.head.take() {
let result;
if i == 0 {
result = Some(h.val);
self.head = h.next;
} else {
result = h.remove(i);
self.head = Some(h);
}
self.size -= 1;
result
} else {
None
}
}
pub fn prepend(&mut self, v: V) {
let next;
if let Some(n) = self.head.take() {
next = Some(n);
} else {
next = None;
}
self.size += 1;
self.head = Some(Box::new(Node{val: v, next: next}));
}
pub fn append(&mut self, v: V) {
let mut head;
if let Some(mut n) = self.head.take() {
n.append(v);
head = Some(n);
} else {
head = Some(Box::new(Node{val: v, next: None}));
}
self.size += 1;
self.head = head;
}
pub fn insert(&mut self, i: usize, v: V) -> Option<V> {
let result;
if i == self.size {
self.append(v);
result = None;
} else if i == 0 {
self.prepend(v);
result = None;
} else if let Some(mut h) = self.head.take() {
result = match h.insert(i, v) {
Some(r) => Some(r),
None => {
self.size += 1;
None
},
};
self.head = Some(h);
} else {
result = Some(v);
}
result
}
}
impl<V> Node<V> where V: Display + Default {
// used by "print" to print values in order
fn print_order(&self, first: bool) {
if !first {
print!(", ");
}
print!("{}", &self.val);
if let Some(n) = &self.next {
n.print_order(false);
}
}
fn get(&self, i: usize) -> Option<&V> {
if i == 0 {
Some(&self.val)
} else if let Some(n) = &self.next {
n.get(i - 1)
} else {
None
}
}
// I'm certain there is a better way of going about this, but I couldn't think of one
// (at least, not one that wasn't equally as cumbersome)
fn remove(&mut self, i: usize) -> Option<V> {
if i == 1 {
let result;
if let Some(mut next) = self.next.take() {
if let Some(mut after) = next.next.take() {
result = Some(std::mem::replace(&mut next.val, after.val));
next.next = after.next; // Remove this item from within the list
self.next = Some(next);
} else {
result = Some(std::mem::replace(&mut next.val, Default::default()));
self.next = None; // Remove this item from the end of the list
}
} else {
result = None;
}
result
} else if let Some(n) = &mut self.next {
n.remove(i - 1)
} else {
None
}
}
fn append(&mut self, v: V) {
if let Some(mut n) = self.next.take() {
n.append(v);
self.next = Some(n);
} else {
self.next = Some(Box::new(Node{val: v, next: None}));
}
}
fn insert(&mut self, i: usize, v: V) -> Option<V> {
if i == 0 {
if let Some(n) = self.next.take() {
let this_old_val = std::mem::replace(&mut self.val, v);
self.next = Some(Box::new(Node{val: this_old_val, next: Some(n)}));
None
} else {
let this_old_val = std::mem::replace(&mut self.val, v);
self.next = Some(Box::new(Node{val: this_old_val, next: None}));
None
}
} else {
if let Some(mut n) = self.next.take() {
let result = n.insert(i - 1, v);
self.next = Some(n);
result
} else {
Some(v)
}
}
}
}
}
use linked_list::LList;
fn main() {
// Example use
let mut list = LList::<i32>::new();
list.prepend(3);
list.append(4);
list.prepend(2);
list.append(6);
list.insert(3, 5);
let mut list2 = LList::<i32>::new();
list2.append(3);
list2.insert(1, 4);
list2.insert(3, 6); // This is meant to fail
println!("{}", list.len());
list.print();
println!("{}", list2.len());
list2.print();
list.remove(2);
println!("{}", list.len());
list.print();
list.remove(0);
println!("{}", list.len());
list.print();
list.remove(2);
println!("{}", list.len());
list.print();
list.remove(1);
println!("{}", list.len());
list.print();
list.remove(0);
println!("{}", list.len());
list.print();
}
@dbyr
Copy link
Author

dbyr commented Jan 9, 2020

In the third revision, I have tried to make the list more efficient by not continually destroying and creating space in memory.

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