Implementing a doubly linked list with smart pointers

Question

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

• Zeta: You might be interested in Learning Rust With Entirely Too Many Linked Lists. It's a little bit older (~2 years) but still might give you some additional insight.
• Svetlin Zarev: Thanks, I'll definitely take a look at it!

Answer 1

Some quick caveats:

1. Linked Lists are a rarely useful data structure, outside of a learning exercise you should almost never use them.
2. The techniques for implementing typical rust code (which primarily uses already crafted data structures) is quite different from rust code which is actually implementing said data structures. You won't get a real handle on the flavor of rust by implementing things like linked lists.

Having said that, let's look at your code.

impl<T: Debug> Debug for List<T> {
 fn fmt(&self, f: &'_ mut Formatter) -> Result<(), Error> {
 writeln!(f, "List size: {:?}", self.size);

Your output here doesn't look much like the typical Debug output. I would define my own function with its own name for something that's not really compatible with the spirit of Debug.

 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())
 };

Option has a handy map method, which lets you write this as

 let prev = node.borrow().prev.map(|p| p.upgrade().unwrap())

map effectively handles the common case where None maps to None, but you want to do something with the Some case.

 let next = match node.borrow().next {
 None => None,
 Some(ref n) => Some(Rc::clone(n))
 };

You could use map again here. But there is an even simpler option:

let next = node.borrow().next.clone()

All you are doing is clone a Optional Rc, which is handled by the clone method.

 let p_val = match prev {
 None => None,
 Some(ref t) => Some(Rc::clone(&t.borrow().value))
 };

Rather then fetching prev and then p_val it'll more succinct if you do it all in one.

 let p_val = node.borrow().prev.map(|p| Rc::clone(p.upgrade().unwrap().value))

Moving on:

 let n_val = match next {
 None => None,
 Some(ref t) => Some(Rc::clone(&t.borrow().value))
 };

There is a function called Ref::map which maps a reference (returned from RefCell borrow into a computed value. This allow the following:

 let n_val = next.as_ref().map(|t| Ref::map(t.borrow(), |s| &s.value));

This is somewhat harder to follow, but the benefit is that we avoid calling clone on the value.

 let c_val = Rc::clone(&node.borrow().value);

This clone is simply unnecessary. it can be removed.

 writeln!(f, "{:?} <<--prev--<< {:?} >>--next-->> {:?}", p_val, c_val, n_val);

writeln returns an error that you should be checking for and returning on failure.

 match next {
 None => break,
 Some(ref t) => node = Rc::clone(t),
 }
 }

break at the end of a loop is usually a sign that there is a better way to structure your loop. In particular, something like this:

 let mut next_node = self.head.clone();
 while let Some(node) = next_node {
 next_node = node.borrow().next.clone()
 // do whatever you need to
 }

If you do this, you can skip checking for a None head pointer and avoid the break. Your loop will be much simpler.

 }
 return Ok(());
 }
}
#[derive(Debug)]
struct Node<T> {
 next: Option<NextNode<T>>,
 prev: Option<PrevNode<T>>,
 value: Rc<T>,
}

In response to question about Box vs Rc, the answer is neither. Just store a T. One of the performance advantages of Rust is that it can often store data directly inline with other data, not via indirections like Box and Rc.

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));
 }
 }

I'd do this more like

 let node = Rc::new(Node {
 next: self.head.clone(),
 prev: None,
 value: Rc::new(value)
 })
 if let Some(head) = self.head {
 head.borrow_mut().prev = Some(Rc::downgraph(&node));
 }

Which I think simplifies it a bit.

 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,
 }));
 }
}