I'm learning Rust and I enjoy implementing linked lists (and other data structures) to validate my understanding when learning a language. I know Rust is not very friendly with cyclical structures and this demotivated me a lot (I dropped this list implementation several times), but I was able to come up with a working code (sort of).

I would like to know if the following list implementation is a good code for a list implementation in Rust or if I should be using other structures (I know there is a guide to implement linked lists in rust and I read a part of that guide, but I decided to practice before I finished reading it).

use std::cell::RefCell;
use std::rc::Rc;
struct List {
    head: Option<Rc<RefCell<Node>>>,
    tail: Option<Rc<RefCell<Node>>>
}

struct Node {
    element: i32,
    next: Option<Rc<RefCell<Node>>>
}

impl List {
    fn new() -> List {
        List {head: None, tail: None}
    }

    fn append(self: &mut List, value: i32) {
        if Option::is_none(&self.head) {
            let node = Rc::new(RefCell::new(Node {element: value, next: None}));
            self.head = Some(node);
            self.tail = self.head.clone();
        } else {
            let new_node = Rc::new(RefCell::new(Node {element: value, next: None}));
            if let Some(tail) = &self.tail {
                tail.borrow_mut().next = Some(Rc::clone(&new_node));
            }
            self.tail = Some(new_node);
        }
    }

    fn delete_by_index(self: &mut List, index: usize) {
        let mut current = self.head.clone();
        let mut i: usize = 0;
        let mut prev: Option<Rc<RefCell<Node>>> = None;
        while current.is_some() && i < index{
            prev = current.clone();
            current = current.unwrap().borrow().next.clone();
            i += 1;
        }
        if let Some(node) = prev {
            node.borrow_mut().next = current.unwrap().borrow().next.clone();
            if node.borrow().next.is_none() {
                self.tail = Some(node.clone());
            }
        } else {
            self.head = current.unwrap().borrow().next.clone();
        }
    }

    fn display(&self) {
        let mut current = self.head.clone();
        while let Some(node) = current {
            let borrowed = node.borrow();
            println!("{}", borrowed.element);
            current = borrowed.next.clone();
        }
    }
}

You can see I'm using a lot of Rc and this is because I have head and tail which can point to the same node, so this should be a shared address.

I'm also using a lot of clone/unwrap/borrow/borrow_mut. Is there a way to avoid having all these calls ? They seem overly complex. I know I could use the let Some(node) = self.head syntax, but I considered it more complex to reason about the nodes (it could be a lack of practice though).

Overall, I feel Rust really demotivating to implement such structures if compared to C, but I'm trying to enjoy the language.

9 posts - 4 participants

Read full topic