I've been learning Rust for the past few days and I just passed the "Smart Pointers" chapter. To check what I've learned I've decided to implement a doubly linked list.
My question is, is this appropriate way to implement one and what can be improved? Which is better - using Rc<T>
or Box<T>
for the node values?
lib.rs
use std::rc::{Rc, Weak};
use std::cell::RefCell;
use std::fmt::Debug;
use std::fmt::Formatter;
use std::fmt::Error;
type NextNode<T> = Rc<RefCell<Node<T>>>;
type PrevNode<T> = Weak<RefCell<Node<T>>>;
pub struct List<T> {
head: Option<NextNode<T>>,
tail: Option<PrevNode<T>>,
size: usize,
}
impl<T: Debug> Debug for List<T> {
fn fmt(&self, f: &'_ mut Formatter) -> Result<(), Error> {
writeln!(f, "List size: {:?}", self.size);
if let Some(ref h) = self.head {
let mut node = Rc::clone(h);
loop {
let prev = match node.borrow().prev {
None => None,
Some(ref p) => Some(p.upgrade().unwrap())
};
let next = match node.borrow().next {
None => None,
Some(ref n) => Some(Rc::clone(n))
};
let p_val = match prev {
None => None,
Some(ref t) => Some(Rc::clone(&t.borrow().value))
};
let n_val = match next {
None => None,
Some(ref t) => Some(Rc::clone(&t.borrow().value))
};
let c_val = Rc::clone(&node.borrow().value);
writeln!(f, "{:?} <<--prev--<< {:?} >>--next-->> {:?}", p_val, c_val, n_val);
match next {
None => break,
Some(ref t) => node = Rc::clone(t),
}
}
}
return Ok(());
}
}
#[derive(Debug)]
struct Node<T> {
next: Option<NextNode<T>>,
prev: Option<PrevNode<T>>,
value: Rc<T>,
}
impl<T> List<T> {
pub fn new() -> List<T> {
return List {
head: None,
tail: None,
size: 0,
};
}
pub fn push_head(&mut self, value: T) {
let boxed_value = Rc::new(value);
let new_node = Node::new_unlinked(boxed_value);
let back_link = Some(Rc::downgrade(&new_node));
match self.head {
None => {
self.tail = back_link;
}
Some(ref mut h) => {
h.borrow_mut().prev = back_link;
new_node.borrow_mut().next = Some(Rc::clone(h));
}
}
self.head = Some(new_node);
self.size += 1;
}
pub fn push_tail(&mut self, value: T) {
let boxed_value = Rc::new(value);
let new_node = Node::new_unlinked(boxed_value);
let weak_link = Some(Rc::downgrade(&new_node));
match self.tail {
None => {
self.head = Some(new_node);
}
Some(ref t) => {
new_node.borrow_mut().prev = Some(Weak::clone(t));
let next_ref = t.upgrade().unwrap();
next_ref.borrow_mut().next = Some(new_node);
}
}
self.tail = weak_link;
self.size += 1;
}
}
impl<T> Node<T> {
fn new_unlinked(value: Rc<T>) -> NextNode<T> {
return Rc::new(RefCell::new(Node {
next: None,
prev: None,
value,
}));
}
}
main.rs
extern crate linkedlist;
use linkedlist::List;
fn main() {
let mut list: List<i32> = List::new();
list.push_head(3);
list.push_head(2);
list.push_head(1);
list.push_tail(4);
list.push_tail(5);
list.push_tail(6);
println!("{:#?}", list);
}
Debug output:
List size: 6
None <<--prev--<< 1 >>--next-->> Some(2)
Some(1) <<--prev--<< 2 >>--next-->> Some(3)
Some(2) <<--prev--<< 3 >>--next-->> Some(4)
Some(3) <<--prev--<< 4 >>--next-->> Some(5)
Some(4) <<--prev--<< 5 >>--next-->> Some(6)
Some(5) <<--prev--<< 6 >>--next-->> None