Implementing Doubly Linked List in Rust

Doubly linked list is a data structure similar to singly linked list, but with the addition of bidirectional connections between pairs of nodes. Before leaning about the data structure I had no idea what we can do with it. However, it’s truly amazing when combining it with other data structure such as hashmap.

LeetCode provides an interesting problem that requires implementing your own LRU cache. I managed to solved it by utilizing the doubly linked list data structure. As you can imagine, writing linked list in Rust is challenging since it involves dealing with many Rc and RefCell. Nonetheless, tackling this problem for a week taught me a great deal. To be honest, I use this beautiful solution as a reference to solve it, but with some slight changes as follows:

Avoid unwrapping

It’s not ideal to use .unwrap() to get the data inside Result and Option so I work it around with different approach, mainly pattern matching.

// Instead of:
if tail.is_some() {
    tail.as_ref().unwrap().borrow_mut().next = Some(node.clone());
}

// We can do this:
if let Some(tail) = &tail {
    tail.borrow_mut().next = Some(node.clone());
}

Avoid deep cloning

According to The Rust Book , it’s a convention to use Rc::clone(&node) to copy a pointer of an RC. So I tried to avoid .clone() as much as possible so that it could minimize the cost:

// Instead of:
self.remove(target.clone());

// We can do this:
self.remove(Rc::clone(&target));

As you can see it makes the code longer and eventually might affect code’s readability. But it’s a recommended way as it doesn’t deep-copy the data.

And here is my solution:

(I couldn’t finish it without the help of code editor 😿)

use std::{cell::RefCell, collections::HashMap, fmt::Display, rc::Rc};

struct LRUCache {
    capacity: usize,
    cache: HashMap<i32, Rc<RefCell<LinkedNode>>>,
    dll: DoublyLinkedList,
}

impl LRUCache {
    fn new(capacity: i32) -> Self {
        Self {
            capacity: capacity as usize,
            cache: HashMap::new(),
            dll: DoublyLinkedList::new(),
        }
    }

    fn get(&mut self, key: i32) -> i32 {
        if let Some(node) = self.cache.get(&key) {
            // Cache hit -> update doubly linked list
            self.dll.move_to_tail(Rc::clone(&node));
            return node.borrow().val.clone();
        }
        -1
    }

    fn put(&mut self, key: i32, value: i32) {
        match self.cache.get(&key) {
            Some(node) => {
                node.borrow_mut().val = value;
                self.dll.move_to_tail(Rc::clone(&node));
            }
            None => {
                let new_node = Rc::new(RefCell::new(LinkedNode::new(key, value)));
                self.cache.insert(key, Rc::clone(&new_node));
                self.dll.push_tail(Rc::clone(&new_node));
                if self.capacity < self.cache.len() {
                    let key = self.dll.pop_head();
                    self.cache.remove(&key);
                }
            }
        }
    }
}

struct DoublyLinkedList {
    head: Option<Rc<RefCell<LinkedNode>>>,
    tail: Option<Rc<RefCell<LinkedNode>>>,
}

impl DoublyLinkedList {
    pub fn new() -> Self {
        Self {
            head: None,
            tail: None,
        }
    }

    fn get_head(&self) -> Option<Rc<RefCell<LinkedNode>>> {
        match &self.head {
            Some(head) => Some(Rc::clone(head)),
            None => None,
        }
    }

    fn get_tail(&self) -> Option<Rc<RefCell<LinkedNode>>> {
        match &self.tail {
            Some(tail) => Some(Rc::clone(tail)),
            None => None,
        }
    }

    pub fn push_tail(&mut self, node: Rc<RefCell<LinkedNode>>) {
        match &self.get_tail() {
            Some(prev_tail) => {
                prev_tail.borrow_mut().next.replace(Rc::clone(&node));
                node.borrow_mut().prev = Some(Rc::clone(&prev_tail));
            }
            None => {
                // This node should be the 1st node
                node.borrow_mut().prev = None;
                self.head = Some(Rc::clone(&node));
            }
        }
        node.borrow_mut().next = None;
        self.tail = Some(Rc::clone(&node));
    }

    pub fn move_to_tail(&mut self, node: Rc<RefCell<LinkedNode>>) {
        self.remove(Rc::clone(&node));
        self.push_tail(Rc::clone(&node));
    }

    pub fn pop_head(&mut self) -> i32 {
        if let Some(head) = &self.head {
            return self.remove(Rc::clone(&head));
        }
        -1
    }

    pub fn remove(&mut self, node: Rc<RefCell<LinkedNode>>) -> i32 {
        let prev = self.get_prev(Rc::clone(&node));
        let next = self.get_next(Rc::clone(&node));
        let key = node.borrow().key;
        match (prev, next) {
            (Some(prev), Some(next)) => {
                // node was in the middle of doubly linked list
                prev.borrow_mut().next.replace(Rc::clone(&next));
                next.borrow_mut().prev.replace(Rc::clone(&prev));
            }
            (Some(prev), None) => {
                // The node should be the tail
                prev.borrow_mut().next.take();
                self.tail.replace(Rc::clone(&prev));
            }
            (None, Some(next)) => {
                // The node should be the head
                next.borrow_mut().prev.take();
                self.head.replace(Rc::clone(&next));
            }
            (None, None) => {
                // The node should be head and tail
                self.head.take();
                self.tail.take();
            }
        }
        key
    }

    fn get_prev(&self, node: Rc<RefCell<LinkedNode>>) -> Option<Rc<RefCell<LinkedNode>>> {
        match &node.borrow().prev {
            Some(prev) => Some(Rc::clone(&prev)),
            None => None,
        }
    }

    fn get_next(&self, node: Rc<RefCell<LinkedNode>>) -> Option<Rc<RefCell<LinkedNode>>> {
        match &node.borrow().next {
            Some(next) => Some(Rc::clone(&next)),
            None => None,
        }
    }
}

struct LinkedNode {
    key: i32,
    val: i32,
    prev: Option<Rc<RefCell<LinkedNode>>>,
    next: Option<Rc<RefCell<LinkedNode>>>,
}

impl LinkedNode {
    pub fn new(key: i32, val: i32) -> Self {
        Self {
            key,
            val,
            prev: None,
            next: None,
        }
    }
}

Thanks for reading ✌️