4
\$\begingroup\$

I have just started learning Rust, and in order to try to get the hang of references, ownership and mutability, I have attempted to make a doubly linked list. It now compiles, and the add function seems to be working as intended.

There is one implementation detail that I am curious about, and in general I'm wondering whether my code violates any good practice. Also, related to this, have I painted myself into any kind of corner if I want to extend this code? (Making add() keep the list ordered, using generics, implementing Iterator, and so on.)

use std::rc::{Rc, Weak};
use std::cell::RefCell;

#[derive(Debug)]
struct Node {
    value: i32,
    next: RefCell<Option<Rc<Node>>>,
    prev: RefCell<Weak<Node>>,
}

impl Node {
    pub fn add(&self, this: &Rc<Node>, i: i32) {
        if let Some(ref r) = *self.next.borrow() {
            r.add(r, i);
            return;
        };
        *self.next.borrow_mut() = Some(Rc::new(Node {
            value: i,
            next: RefCell::new(None),
            prev: RefCell::new(Rc::downgrade(&this)),
        }));
    }
}

#[derive(Debug)]
struct List {
    head: RefCell<Option<Rc<Node>>>,
}

impl List {
    pub fn add(&self, i: i32) {
        if let Some(ref r) = *self.head.borrow() {
            r.add(r, i);
            return;
        };
        *self.head.borrow_mut() = Some(Rc::new(Node {
            value: i,
            next: RefCell::new(None),
            prev: RefCell::new(Weak::new()),
        }));
    }
}

fn main() {
    let list = List {
        head: RefCell::new(None),
    };
    println!("{:?}", list);
    list.add(1);
    list.add(2);
    println!("{:?}", list);
}

The detail I'm curious about is whether the if let parts can be done with a match. Or, more specifically, can it be done without the extra return call. No matter what I tried (both match and if let with else), the borrow() got in the way of the borrow_mut() in the None arm, and I couldn't get the pattern matching to work without the borrow().

\$\endgroup\$
3
\$\begingroup\$

Before looking at your code, I want to give a general notice: don't use linked lists. They are almost always the wrong choice of data structure. They are useful primarily pedagogically.

Furthermore, I should warn you that implementing a doubly-linked list will not look like typical Rust. You can't implement a doubly-linked list in Rust without using escape hatches like Rc, RefCell, or raw pointers. These escape hatches are necessary when doing low level things like implementing a data structure, but normal Rust code avoids them as much as possible. If you want to get used to "thinking in Rust" you should pick a different exercise.

The first thing about your code I note is that Node::add function. It takes a pointer to itself twice. self and this. Having two different pointers to the same thing is unhelpful. Just drop the &self parameter and refer to this consistently in the function. Then you can call the function as Node::add.

The second thing is that you have RefCells containing Rc's. However, the standard way is to have it the other way around. It should be Rc<RefCell<?>> not RefCell<Rc<?>>. You'll find that your current design does not let you modify the value of each node.

A third thing is the lack of mutable references. Your add method allows adding to your list without the list being mutable. That doesn't really make sense, your add method really should take a mutable reference to the list. You get away with this because of the previous point.

Finally, you would be better off not using recursion to add the item to the end of list. Recursion is much slower than iteration. It would make more sense to scan through the nodes looking for the end of the list in a loop than in a recursive function call.

\$\endgroup\$
3
  • \$\begingroup\$ Thank you for the answer. I will have to wait until tomorrow to actually sit down and try to implement the changes, but I have a few immediate responses. Yes, linked lists are terrible performance-wise. This is mostly a result from following the Rust Book (which doesn't really have exercises) and trying to follow chapter 15 about smart pointers (which isn't what my question said, sorry). That's also why I used RefCell<Rc<T>>; they use in their tree example. I guess using RefCell<Rc<T>> means I have to make a whole new node if I want to change the value. \$\endgroup\$
    – Arthur
    Sep 24 '18 at 5:24
  • 1
    \$\begingroup\$ @Arthur, hmm.. I've opened a ticket about the tree example: github.com/rust-lang/rust/issues/54531, we'll see if they think it's wrong or there is a good reason for it. \$\endgroup\$ Sep 24 '18 at 14:23
  • \$\begingroup\$ Just for reference (so that I can find it later too) @Winston has now filled it at github.com/rust-lang/book/issues/1543 \$\endgroup\$
    – Arthur
    Sep 25 '18 at 5:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.