Why do we need to use Rc<T> from std::rc::Rc for implementing a double-ended static-typed Linked List?

You have seen many implementations of static-typed double-ended LinkedList implementations in Rust, but why each successful implementations require the Rc<T>?

What is a double-ended static-typed Linked List?

A double-ended static-typed linked list is a data structure that allows members of a specified type to be added or removed in constant time from either end of the list. 

It can be implemented in Rust by combining linked list nodes and generics.

Static-typed would mean that all nodes of the linked list are of the same concrete time, e.g. Node<String>, Node<i32>, and others.

Static-typed Linked List, each node contains data of primitive data i32.

What is the reference-counted Rc<T> struct?

The Rust language supports multiple ownership of a value via a form of smart pointer called `Rc<T>` (short for "reference counted pointer"). It keeps track of the number of references to the item and automatically deallocates it when the count is zero.

This is to circumvent the ownership of Rust that only one variable is allowed to own a value. A single value can have numerous owners when using `Rc<T>`, and the reference count makes sure that the value is still valid as long as any of the owners are still in scope.

Naive Implementation of double-ended static-typed Linked List

One might first attempt to implement a double-ended static-typed Linked List in the following manner.

pub struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}

// define a type alias for easy reference
type OptionBoxedNode<T> = Option<Box<Node<T>>>;

// definition of the `LinkedList<T>`
pub struct LinkedList<T> {
    head: OptionBoxedNode<T>,
    tail: OptionBoxedNode<T>,
}

// implementations of `LinkedList<T>` for all generic type `T`
impl<T> LinkedList<T> {
    pub fn new_empty() -> Self {
        Self {
            head: None,
            tail: None,
        }
    }

  pub fn new_with_node(node: Node<T>) -> Self {
    Self {
      head: Some(Box::new(node)),
      tail: None,
    }
  }

  pub fn appendback(&mut self, node: Node<T>) {
    match self.head.take() { // take out the head and leave in its place a None
      Some(mut old_head) => {
        old_head.next = Some(Box::new(node));
        self.tail = Some(Box::new(node));
      }
      None => {
        self.head = Some(Box::new(node));
      }
    }
  }
}

One would encounter an error shown:

error[E0382]: use of moved value: `node`
  --> src/why_use_rc_refcell/why_box_not_works.rs:34:35
   |
30 |   pub fn appendback(&mut self, node: Node<T>) {
   |                            ---- move occurs because `node` has type `Node<T>`, which does not implement the `Copy` trait
...
33 |         old_head.next = Some(Box::new(node));
   |                                       ---- value moved here
34 |         self.tail = Some(Box::new(node));
   |                                   ^^^^ value used here after move

Problem

The problem occurs because the value `node` has been ‘moved’ into the `new()` method of struct `Box` and is therefore consumed by it - it no longer exists. Hence, the `node` variable on Line 34 would not have any value binding to it.

Naive Solution

Well, one might think, surely we can use the `Derive` macro to ‘derive’ the `clone` trait on `Node<T>` to `.clone()` the value of `node` and pass its original value and the cloned value separately into `Box::new()`. However, that would mean when pushing a node into the linked list, `previous_node.next` and `self.tail` of `LinkedList<T>` would be pointing to different values in memory and hence would not be a linked list, so to speak.

Resolution to the Ownership Issue using Rc<T>

We can resolve this problem by using `Rc<T>`. First, we bring the struct `Rc<T>` to scope by declaring:

use std::rc::Rc;

By declaring the above, we effectively bring the struct `Rc<T>` to scope from the standard library.

Next, we amend our implementation to the following:

use std::rc::Rc;

#[derive(Clone)]
pub struct Node<T: Clone> {
    data: T,
    next: Option<Rc<Node<T>>>,
}

type OptionRcNode<T> = Option<Rc<Node<T>>>;

pub struct LinkedList<T: Clone> {
    head: OptionRcNode<T>,
    tail: OptionRcNode<T>,
}

impl<T: Clone> LinkedList<T> {
    pub fn new_empty() -> Self {
        Self {
            head: None,
            tail: None,
        }
    }

  pub fn new_with_node(node: Node<T>) -> Self {
    let mut new_ll = Self::new_empty();
    Self::append(&mut new_ll, node);
    new_ll
  }

  pub fn append(&mut self, node: Node<T>) {
    let appending_node = Rc::new(node);
    match self.tail.take() {
      Some(ref mut old_tail) => { // we match Some(...) and "casts" it to 
// mutable reference of type `Rc<Node<T>>`
        let old_tail = Rc::make_mut(old_tail);
        old_tail.next = Some(Rc::clone(&appending_node));
      }
      None => {
        self.head = Some(Rc::clone(&appending_node));
      }
    }
    self.tail = Some(appending_node);
  }
}

We make new changes to our implementations:

1. Added a trait bound `Clone` to the generic type `T`. This is so that we can derive the trait `Clone` on Node<T> as well.

2. This trait bound is needed for the associated method of `Rc<T>`’s `make_mut()`.

Reasons for these Changes

If we were to simply write for the `append()` method the following:

pub fn append(&mut self, node: Node<T>) {
    let appending_node = Rc::new(node);
    match self.tail.take() {
      Some(old_tail) => {
        old_tail.next = Some(Rc::clone(&appending_node));
      }
      None => {
        self.head = Some(Rc::clone(&appending_node));
      }
    }
    self.tail = Some(appending_node);
  }

We would be unable to compile due to this error:

error[E0594]: cannot assign to data in an `Rc`
  --> src\why_use_rc\why_rc_works.rs:35:9
   |
35 |         old_head.next = Some(Rc::clone(&appending_node));
   |         ^^^^^^^^^^^^^ cannot assign
   |
   = help: trait `DerefMut` is required to modify through a dereference, but it is not implemented for `Rc<why_rc_works::Node<T>>`

We encounter this error because, in Rust, references are of two ‘subtypes’, the immutable reference and the mutable reference. The reference counting enabled by the struct `Rc<T>` counts the immutable references given out to values and the borrowing rules of Rust are enforced during compile time.

Here are the borrowing rules of Rust (from the Rust Book):

• At any given time, you can have either one mutable reference or any number of immutable references.

• References must always be valid.

`Node<T>.next` is of type `Option<Rc<Node<T>>>`, `Some(…)` takes care of the `Option` enum, so we are trying to mutate next such that it now points to a new `Option<Rc<Node<T>>>` where the instance of `Node<T>` is `appending_node`.

Hence, to overcome this compile error, we make use of the `Rc::make_mut()` associated function and make tweaks to the generic type `T` by imposing trait bound `Clone` on it.

We can also write some tests to make sure our implementation works.

#[cfg(test)]
mod tests {

    use super::*;

    #[test]
    fn test_ll_new_empty() {
        let ll = LinkedList::<u32>::new_empty();
        assert!(ll.head.is_none() && ll.tail.is_none());
    }

  #[test]
  fn test_ll_new_with_node() {
    let new_node = Node {
      data: 16,
      next: None,
    };
    let ll = LinkedList::new_with_node(new_node);
    assert_eq!(ll.head.unwrap().data, 16);
    assert_eq!(ll.tail.unwrap().data, 16);
  }

  #[test]
  fn test_ll_append() {
    let new_node = Node {
      data: 16,
      next: None,
    };
    let mut ll = LinkedList::new_with_node(new_node);
    ll.append( Node {data: 17, next: None} );
    assert_eq!(ll.head.unwrap().next.as_ref().unwrap().data, 17);
  }
}

We can run these tests by running the CLI command: `cargo test` on our favourite terminal.

We will see this error after running `cargo test`.

    Finished test [unoptimized + debuginfo] target(s) in 0.01s
     Running unittests src\lib.rs (target\debug\deps\why_use_rc_refcell_for_linkedlist-787cc8ba0a0d610b.exe)

running 3 tests
test why_use_rc::why_rc_works::tests::test_ll_new_empty ... ok
test why_use_rc::why_rc_works::tests::test_ll_new_with_node ... ok
test why_use_rc::why_rc_works::tests::test_ll_append ... FAILED

failures:

---- why_use_rc::why_rc_works::tests::test_ll_append stdout ----
thread 'why_use_rc::why_rc_works::tests::test_ll_append' panicked at 'called `Option::unwrap()` on a `None` value', src\why_use_rc\why_rc_works.rs:76:47 
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace


failures:
    why_use_rc::why_rc_works::tests::test_ll_append

test result: FAILED. 2 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

error: test failed, to rerun pass `--lib`

Reason for the Failure of the `append()` Method

According to the documentation of `Rc::make_mut()`, if there are references pointing to the variable of type `Rc<T>`, i.e. the reference count is not zero, the associated function then clones the inner value of generic type `T` and allocates it to elsewhere.

let old_tail = Rc::make_mut(old_tail);
old_tail.next = Some(Rc::clone(&appending_node));

Essentially, what the above two lines are doing is the following:

1. Make a copy of `old_tail` because it still has references pointing to it.

2. Set the field `next` of `old_tail` to `Some(Rc<Node<T>)`.

Hence, when the tests try to access the next node after `self.head`, it gets None because `self.tail.next` is None.

What do we really need?

To implement a double-ended static-typed Linked List, we need two things:

1. Each `Node<T>` can be owned by multiple owners, that’s why we are using `Rc<T>`.

2. But, we would also need to **mutate** the value of type `Node<T>` despite having multiple owners to the value.

These violate the Ownership Rules of Rust during Compile Time.

Summary and Solution: RefCell<T>

1. We tried to understand why we need the struct `Rc<T>` to implement a double-ended static-typed Linked List.

2. We do so by implementing one using the regular `Box<T>` and see that it cannot be used because of the Ownership Rules.

3. We then move to use `Rc<T>` which “sidesteps” the Ownership Rules by using reference counting.

4. Finally, we encounter an issue with mutability when we need to mutate the inner type wrapped by `Rc<T>` but were unable to do so.

Solution

The solution will come from the struct `RefCell<T>` which offers the interior mutability pattern. And we will go through this in the next article. You can also see the above codes on my Github Repo.

Resources

1. Tutorials by [Ryan Levick]() on [YouTube](https://www.youtube.com/@RyanLevicksVideos) (excellent teacher for Rust). Two relevant videos are:

   * LinkedList

   * Static vs. Dynamic dispatch

2. Hands-on data structures and algorithms with Rust learn programming techniques to build effective, maintainable, and readable code in Rust 2018 by Matzinger, Claus; Chapter titled: Lists, Lists, and More Lists. ([Amazon](https://www.amazon.com/Hands-Data-Structures-Algorithms-Rust-ebook/dp/B07N7D6PG4/))

3. The Complete Rust Programming Reference Guide by Rahul Sharma, Vesa Kaihlavirta and Claus Matzinger; Chapter 14. ([Amazon](https://www.amazon.com/Complete-Rust-Programming-Reference-Guide/dp/1838828109))

4. [Implementing a Linked List in Rust](https://medium.com/swlh/implementing-a-linked-list-in-rust-c25e460c3676)

5. [Learn Rust With Entirely Too Many Linked Lists](https://rust-unofficial.github.io/too-many-lists/)

6. The Rust Book; [Chapter 15](https://doc.rust-lang.org/book/ch15-05-interior-mutability.html) (on `RefCell` and the `Interior Mutability` Pattern)