1.前言
C++中有一个智能指针的概念实现，其中共享指针底层实现原理就是使用引用计数的方式。
而rust中同样也有类似的概念实现。
本文将通过实现一个简单的双向链表来理解Rust中的引用计数 (Rc)、引用单元 (RefCell) 和内部可变性 (Interior Mutability) 。
双向链表是一种常见的数据结构，它允许我们在节点之间向前或向后遍历。为了实现双向链表，我们需要存储指向下一个和前一个节点的指针。
但由于Rust所有权的闲置，这会导致直接使用引用 (reference) 可能会导致悬垂指针 (dangling pointer) 问题，这在 Rust 中是无法编译通过的。
2.使用智能指针Rc和RefCell
为了克服这些问题，Rust 提供了智能指针类型，例如 Rc 和 RefCell。
Rc(Reference Counting) 用于共享所有权。它允许多个地方引用同一个数据，并会在引用计数为零时自动释放内存。RefCell(Reference Cell) 提供可变借用 (mutable borrow) 的功能。虽然Rc本身只能进行不可变借用，但通过RefCell包装数据，我们可以实现对内部数据的可变访问。
首先我们来定义链表节点结构体：
struct Node<T> {
data: T,
prev: Option<NodeRef<T>>,
next: Option<NodeRef<T>>,
}
type NodeRef<T> = Rc<RefCell<Node<T>>>;
在这段代码中，我们定义了 Node 结构体，用来表示双向链表中的节点。
data字段存储节点的实际数据。prev和next字段分别存储指向链表中前一个和后一个节点的指针。NodeRef类型是Rc<RefCell<Node<T>>>的别名。它表示对Node<T>的引用计数指针，并将其内部数据用RefCell包装，允许可变借用。
然后定义双向链表：
struct DoublyLinkedList<T> {
head: NodeRef<T>,
}
impl<T> DoublyLinkedList<T> {
fn new(data: T) -> Self {
Self {
head: Rc::new(RefCell::new(Node::new(data))),
}
}
}
在 DoublyLinkedList 结构体中，我们使用 head 字段存储指向链表头结点的指针 (NodeRef<T>)。 new 函数负责创建链表，它通过 Rc::new 创建一个引用计数为 1 的 Node 对象，并将其用 RefCell 包装，最后将该引用赋值给 head 字段。
3.内部可变性
虽然 Rc 本身只能进行不可变借用，但通过 RefCell 的 borrow_mut 方法，我们可以获取对内部数据的可变借用。
比如实现尾部插入数据的操作：
fn append(&mut self, data: T) {
let tail = Self::get_tail(self.head.clone());
let new_node = Rc::new(RefCell::new(Node::new(data)));
new_node.borrow_mut().prev = Some(tail.clone());
tail.borrow_mut().next = Some(new_node);
}
append 函数用于向链表尾部添加新节点。
- 首先，我们调用
get_tail找到链表的尾节点。 - 创建一个新的
Node对象并将其用Rc和RefCell包装。 - 然后，使用
borrow_mut获取对新节点内部数据的可变借用，并设置其prev字段指向尾节点。 - 最后，同样使用
borrow_mut获取对尾节点内部数据的可变借用，并设置其next字段指向新节点。
通过 RefCell 的 borrow_mut 方法，我们可以在保持所有权不变的情况下修改内部数据。
上面用到了一个get_tail函数，代码如下：
fn get_tail(node: NodeRef<T>) -> NodeRef<T> {
match &node.borrow().next {
Some(next) => Self::get_tail(next.clone()),
None => node.clone(),
}
}
get_tail 函数用于查找链表的尾节点。它接收一个 NodeRef<T> 类型的参数 node，表示当前正在检查的节点。
node.borrow().next获取当前节点的next字段。由于next是Option<NodeRef<T>>类型，我们需要使用match表达式进行模式匹配。- 如果
next是Some(next)，表示当前节点不是尾节点，那么我们递归调用get_tail(next.clone())，继续查找下一个节点。这里clone()是必要的，因为它克隆了Rc指针，增加了引用计数，使得我们可以在递归调用中使用next。 - 如果
next是None，表示当前节点是尾节点，那么我们返回node.clone()。同样，clone()克隆了Rc指针，使得调用者可以持有尾节点的所有权。
这个递归过程会一直进行，直到找到 next 字段为 None 的节点，即尾节点。
4.遍历链表
遍历节点的代码如下：
fn main() {
let mut list = DoublyLinkedList::new("head");
// ... (链表节点初始化代码省略)
let mut node = list.head();
loop {
println!("{}", node.borrow().data());
if node.borrow().next.is_none() {
break;
} else {
let next_item = node.borrow().next.as_ref().unwrap().clone();
node = next_item;
}
}
println!("====================");
let mut node = list.tail();
loop {
println!("{}", node.borrow().data());
if node.borrow().prev.is_none() {
break;
} else {
let prev_item = node.borrow().prev.as_ref().unwrap().clone();
node = prev_item;
}
}
}
这段代码演示了如何正向和反向遍历链表。
- 我们首先从
list.head()获取头节点。 - 在循环中，我们使用
node.borrow().data()获取当前节点的数据并打印。 - 然后，通过
node.borrow().next.as_ref().unwrap().clone()获取下一个节点的Rc指针，并将其赋值给node，从而移动到下一个节点。注意这里需要clone()，因为我们需要拥有Rc的所有权才能在下次循环中使用。as_ref()将Option<Rc<RefCell<Node<T>>>>转换为Option<&Rc<RefCell<Node<T>>>>，unwrap()解包Option，因为在循环中我们已经确保了next不为None。 - 反向遍历的逻辑类似，只是使用
prev字段来移动到前一个节点。
5.总结
我们学习了如何使用 Rc 和 RefCell 在 Rust 中实现双向链表。Rc 允许我们共享所有权，而 RefCell 提供了内部可变性的能力，使我们能够在共享所有权的情况下修改数据。
虽然使用 Rc 和 RefCell 可以实现双向链表，但它也有一些缺点，例如运行时借用检查 (runtime borrow checking) 的开销。
在某些情况下，使用 unsafe 代码或其他方法可能会更有效率，但不建议在没有足够把握的情况下随意使用unsafe块，否则很容易引入莫名的bug。
完整代码如下:
use std::cell::RefCell;
use std::rc::Rc;
struct Node<T> {
data: T,
prev: Option<NodeRef<T>>,
next: Option<NodeRef<T>>,
}
type NodeRef<T> = Rc<RefCell<Node<T>>>;
struct DoublyLinkedList<T> {
head: NodeRef<T>,
}
impl<T> Node<T> {
fn new(data: T) -> Self {
Self {
data: data,
prev: None,
next: None,
}
}
fn data(&self) -> &T {
&self.data
}
}
impl<T> DoublyLinkedList<T> {
fn new(data: T) -> Self {
Self {
head: Rc::new(RefCell::new(Node::new(data))),
}
}
fn head(&self) -> NodeRef<T> {
self.head.clone()
}
fn tail(&self) -> NodeRef<T> {
Self::get_tail(self.head.clone())
}
fn get_tail(node: NodeRef<T>) -> NodeRef<T> {
match &node.borrow().next {
Some(next) => Self::get_tail(next.clone()),
None => node.clone(),
}
}
fn append(&mut self, data: T) {
let tail = Self::get_tail(self.head.clone());
let new_node = Rc::new(RefCell::new(Node::new(data)));
new_node.borrow_mut().prev = Some(tail.clone());
tail.borrow_mut().next = Some(new_node);
}
}
fn main() {
let mut list = DoublyLinkedList::new("head");
list.append("123");
list.append("456");
list.append("789");
let mut node = list.head();
loop {
println!("{}", node.borrow().data());
if node.borrow().next.is_none() {
break;
} else {
let next_item = node.borrow().next.as_ref().unwrap().clone();
node = next_item;
}
}
println!("====================");
let mut node = list.tail();
loop {
println!("{}", node.borrow().data());
if node.borrow().prev.is_none() {
break;
} else {
let prev_item = node.borrow().prev.as_ref().unwrap().clone();
node = prev_item;
}
}
}
