When we interact with an Rc type, the following changes happen to it internally:

• When you take a new shared reference to Rc by calling Clone(), Rc increments its internal reference count. Rc internally uses the Cell type for its reference counts
• When the reference goes out of scope, it decrements it
• When all shared references go out of scope, the refcount becomes zero. At this point, the last drop call on Rc does its deallocation

Using reference counted containers gives us more flexibility in the implementation: we can hand out copies of our value as if it were a new copy without having to keep exact track of when the references go out of scope. That doesn't mean that we can mutably alias the inner values.

Rc<T> is mostly used via two methods:

• The static method Rc::new makes a new reference counted container.
• The clone method increments the strong reference count and hands out a new Rc<T>.

Rc internally keeps two kinds of references: strong (Rc<T>) and weak (Weak<T>). Both keep a count of how many references of each type have been handed out, but only when the strong reference count reaches zero so that the values get deallocated. The motivation for this is that an implementation of a data structure may need to point to the same thing multiple times. For instance, an implementation of a tree might have references to both the child nodes and the parent, but incrementing the counter for each reference would not be correct and would lead to reference cycles. The following diagram illustrates the reference cycle situation:

In the preceding diagram, we have two variables, var1 and var2, that reference two resources, Obj1 and Obj2. Along with that, Obj1 also has a reference to Obj2 and Obj2 has a reference to Obj1. Both Obj1 and Obj2 have reference count of 2 when var1 and var2 goes out of scope, the reference count of Obj1 and Obj2 reaches 1. They won't get freed because they still refer to each other.

The reference cycle can be broken using weak references. As another example, a linked list might be implemented in such a way that it maintains links via reference counting to both the next item and to the previous. A better way to do this would be to use strong references to one direction and weak references to the other.

Let's see how that might work. Here's a minimal implementation of possibly the least practical but best learning data structure, the singly linked list:

// linked_list.rs

use std::rc::Rc; 

#[derive(Debug)] 
struct LinkedList<T> { 
    head: Option<Rc<Node<T>>> 
} 

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

impl<T> LinkedList<T> { 
    fn new() -> Self { 
        LinkedList { head: None } 
    } 

    fn append(&self, data: T) -> Self { 
        LinkedList { 
            head: Some(Rc::new(Node { 
                data: data, 
                next: self.head.clone() 
            })) 
        } 
    } 
} 

fn main() { 
    let list_of_nums = LinkedList::new().append(1).append(2); 
    println!("nums: {:?}", list_of_nums); 

    let list_of_strs = LinkedList::new().append("foo").append("bar"); 
    println!("strs: {:?}", list_of_strs); 
}

The linked list is formed of two structs: LinkedList provides a reference to the first element of the list and the list's public API, and Node contains the actual elements. Notice how we're using Rc and cloning the next data pointer on every append. Let's walk through what happens in the append case:

1. LinkedList::new() gives us a new list. Head is None.
2. We append 1 to the list. Head is now the node that contains 1 as data, and next is the previous head: None.
3. We append 2 to the list. Head is now the node that contains 2 as data, and next is the previous head, the node that contains 1 as data.

The debug output from println! confirms this:

nums: LinkedList { head: Some(Node { next: Some(Node { next: None, data: 1 }), data: 2 }) }
strs: LinkedList { head: Some(Node { next: Some(Node { next: None, data: "foo" }), data: "bar" }) }

This is a rather functional form of this structure; every append works by just adding data at the head, which means that we don't have to play with references and actual list references can stay immutable. That changes a bit if we want to keep the structure this simple but still have a double-linked list, since then we actually have to change the existing structure.

You can downgrade an Rc<T> type into a Weak<T> type with the downgrade method, and similarly a Weak<T> type can be turned into Rc<T> using the upgrade method. The downgrade method will always work. In contrast, when calling upgrade on a weak reference, the actual value might have been dropped already, in which case you get a None.

So, let's add a weak pointer to the previous node:

// rc_weak.rs

use std::rc::Rc; 
use std::rc::Weak; 

#[derive(Debug)] 
struct LinkedList<T> { 
    head: Option<Rc<LinkedListNode<T>>> 
} 

#[derive(Debug)] 
struct LinkedListNode<T> { 
    next: Option<Rc<LinkedListNode<T>>>, 
    prev: Option<Weak<LinkedListNode<T>>>, 
    data: T 
} 

impl<T> LinkedList<T> { 
    fn new() -> Self { 
        LinkedList { head: None } 
    } 

    fn append(&mut self, data: T) -> Self { 
        let new_node = Rc::new(LinkedListNode { 
            data: data, 
            next: self.head.clone(), 
            prev: None 
        }); 

        match self.head.clone() { 
            Some(node) => { 
                node.prev = Some(Rc::downgrade(&new_node)); 
            }, 
            None => { 
            } 
        } 

        LinkedList { 
            head: Some(new_node) 
        } 
    } 
} 

fn main() { 
    let list_of_nums = LinkedList::new().append(1).append(2).append(3); 
    println!("nums: {:?}", list_of_nums); 
}

The append method grew a bit; we now need to update the previous node of the current head before returning the newly created head. This is almost good enough, but not quite. The compiler doesn't let us do invalid operations:

We could make append take a mutable reference to self, but that would mean that we could only append to the list if all the nodes' bindings were mutable, forcing the whole structure to be mutable. What we really want is a way to make just one small part of the whole structure mutable, and fortunately we can do that with a single RefCell.

1. Add a use for the RefCell:

        use std::cell::RefCell; 

2. Wrap the previous field in LinkedListNode in a RefCell:

        // rc_3.rs
        #[derive(Debug)] 
        struct LinkedListNode<T> { 
            next: Option<Rc<LinkedListNode<T>>>, 
            prev: RefCell<Option<Weak<LinkedListNode<T>>>>, 
            data: T 
        }

3. We change the append method to create a new RefCell and update the previous reference via the RefCell mutable borrow:

    // rc_3.rs

    fn append(&mut self, data: T) -> Self { 
        let new_node = Rc::new(LinkedListNode { 
            data: data, 
            next: self.head.Clone(), 
            prev: RefCell::new(None) 
        }); 

        match self.head.Clone() { 
            Some(node) => { 
                let mut prev = node.prev.borrow_mut(); 
                *prev = Some(Rc::downgrade(&new_node)); 
            }, 
            None => { 
            } 
        } 

        LinkedList { 
            head: Some(new_node) 
        } 
    } 
} 

Whenever we're using RefCell borrows, it's a good practice to think carefully that we're using it in a safe way, since making mistakes there may lead to runtime panics. In this implementation, however, it's easy to see that we have just the single borrow, and that the closing block immediately discards it.

Apart from shared ownership, we can also get shared mutability at runtime with Rust's concept of interior mutability, which are modeled by special wrapper smart pointer types.