用rust实现简单的双向链表

用rust实现简单的双向链表

📅 2022-03-10 | 🖱️
🔖 rust, 🔖 algorithm

本文将通过实现一个简单的双向链表，理解Rust中的引用计数 (Rc)、引用单元 (RefCell) 和内部可变性 (Interior Mutability) 的概念。

双向链表是一种常见的数据结构，它允许我们在节点之间向前或向后遍历。为了实现双向链表，我们需要存储指向下一个和前一个节点的指针。然而，Rust的所有权系统会带来一些挑战。例如，因为简单使用引用(reference)可能会导致悬垂指针(dangling pointer）问题，这在Rust中是无法编译通过的。

使用智能指针Rc和RefCell #

为了克服这些挑战，Rust提供了智能指针类型，例如 Rc 和 RefCell。

  • Rc (Reference Counting) 用于共享所有权。它允许多个地方引用同一个数据，并会在引用计数为零时自动释放内存。
  • RefCell (Reference Cell) 提供可变借用(mutable borrow)的功能。虽然Rc本身只能进行不可变借用，但通过 RefCell包装数据，我们可以实现对内部数据的可变访问。

代码1：定义链表节点结构体

1struct Node<T> {
2    data: T,
3    prev: Option<NodeRef<T>>,
4    next: Option<NodeRef<T>>,
5}
6
7type NodeRef<T> = Rc<RefCell<Node<T>>>;

在这段代码中，我们定义了Node结构体，用来表示双向链表中的节点。

  • data字段存储节点的实际数据。
  • prev和next字段分别存储指向链表中前一个和后一个节点的指针。
  • NodeRef类型是Rc<RefCell<Node<T>>>的别名。它表示对Node<T>的引用计数指针，并将其内部数据用RefCell包装，允许可变借用。

代码2：定义双向链表

 1struct DoublyLinkedList<T> {
 2    head: NodeRef<T>,
 3}
 4
 5impl<T> DoublyLinkedList<T> {
 6    fn new(data: T) -> Self {
 7        Self {
 8            head: Rc::new(RefCell::new(Node::new(data))),
 9        }
10    }
11}

在DoublyLinkedList结构体中，我们使用head字段存储指向链表头结点的指针 (NodeRef<T>)。 new 函数负责创建链表，它通过 Rc::new 创建一个引用计数为1的Node对象，并将其用RefCell包装，最后将该引用赋值给head字段。

内部可变性 #

虽然Rc本身只能进行不可变借用，但通过RefCell的borrow_mut方法，我们可以获取对内部数据的可变借用。

代码3：尾插操作

1fn append(&mut self, data: T) {
2    let tail = Self::get_tail(self.head.clone());
3    let new_node = Rc::new(RefCell::new(Node::new(data)));
4    new_node.borrow_mut().prev = Some(tail.clone());
5    tail.borrow_mut().next = Some(new_node);
6}

append函数用于向链表尾部添加新节点。

  1. 首先，我们调用 get_tail 找到链表的尾节点。
  2. 创建一个新的Node 对象并将其用Rc和RefCell包装。
  3. 然后，使用borrow_mut 获取对新节点内部数据的可变借用，并设置其prev字段指向尾节点。
  4. 最后，同样使用 borrow_mut获取对尾节点内部数据的可变借用，并设置其next字段指向新节点。

通过RefCell的borrow_mut方法，我们可以在保持所有权不变的情况下修改内部数据。

代码4：get_tail 函数

1fn get_tail(node: NodeRef<T>) -> NodeRef<T> {
2    match &node.borrow().next {
3        Some(next) => Self::get_tail(next.clone()),
4        None => node.clone(),
5    }
6}

get_tail函数用于查找链表的尾节点。它接收一个NodeRef<T>类型的参数node，表示当前正在检查的节点。

  1. node.borrow().next获取当前节点的next 字段。由于next是Option<NodeRef<T>>类型，我们需要使用 match表达式进行模式匹配。
  2. 如果next是Some(next)，表示当前节点不是尾节点，那么我们递归调用get_tail(next.clone())，继续查找下一个节点。这里clone()是必要的，因为它克隆了Rc指针，增加了引用计数，使得我们可以在递归调用中使用next。
  3. 如果next是None，表示当前节点是尾节点，那么我们返回 node.clone()。同样，clone() 克隆了Rc指针，使得调用者可以持有尾节点的所有权。

这个递归过程会一直进行，直到找到next字段为None的节点，即尾节点。

遍历链表 #

代码5：遍历链表

 1fn main() {
 2    let mut list = DoublyLinkedList::new("head");
 3    // ... (链表节点初始化代码省略)
 4    let mut node = list.head();
 5    loop {
 6        println!("{}", node.borrow().data());
 7        if node.borrow().next.is_none() {
 8            break;```rust
 9        } else {
10            let next_item = node.borrow().next.as_ref().unwrap().clone();
11            node = next_item;
12        }
13    }
14    println!("====================");
15    let mut node = list.tail();
16    loop {
17        println!("{}", node.borrow().data());
18        if node.borrow().prev.is_none() {
19            break;
20        } else {
21            let prev_item = node.borrow().prev.as_ref().unwrap().clone();
22            node = prev_item;
23        }
24    }
25}

这段代码演示了如何正向和反向遍历链表。

  • 我们首先从 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字段来移动到前一个节点。

总结 #

我们学习了如何使用Rc和RefCell 在 Rust 中实现双向链表。Rc允许我们共享所有权，而RefCell提供了内部可变性的能力，使我们能够在共享所有权的情况下修改数据。

虽然使用Rc和RefCell可以实现双向链表，但它也有一些缺点，例如运行时借用检查 (runtime borrow checking) 的开销。在某些情况下，使用unsafe代码或其他方法可能会更有效率。然而，对于初学者来说，理解Rc和RefCell是非常重要的，它们是Rust中处理共享可变性的重要工具。

完整代码:

 1use std::cell::RefCell;
 2use std::rc::Rc;
 3
 4struct Node<T> {
 5    data: T,
 6    prev: Option<NodeRef<T>>,
 7    next: Option<NodeRef<T>>,
 8}
 9
10type NodeRef<T> = Rc<RefCell<Node<T>>>;
11
12struct DoublyLinkedList<T> {
13    head: NodeRef<T>,
14}
15
16impl<T> Node<T> {
17    fn new(data: T) -> Self {
18        Self {
19            data: data,
20            prev: None,
21            next: None,
22        }
23    }
24
25    fn data(&self) -> &T {
26        &self.data
27    }
28}
29
30impl<T> DoublyLinkedList<T> {
31    fn new(data: T) -> Self {
32        Self {
33            head: Rc::new(RefCell::new(Node::new(data))),
34        }
35    }
36
37    fn head(&self) -> NodeRef<T> {
38        self.head.clone()
39    }
40
41    fn tail(&self) -> NodeRef<T> {
42        Self::get_tail(self.head.clone())
43    }
44
45    fn get_tail(node: NodeRef<T>) -> NodeRef<T> {
46        match &node.borrow().next {
47            Some(next) => Self::get_tail(next.clone()),
48            None => node.clone(),
49        }
50    }
51
52    fn append(&mut self, data: T) {
53        let tail = Self::get_tail(self.head.clone());
54        let new_node = Rc::new(RefCell::new(Node::new(data)));
55        new_node.borrow_mut().prev = Some(tail.clone());
56        tail.borrow_mut().next = Some(new_node);
57    }
58}
59
60fn main() {
61    let mut list = DoublyLinkedList::new("head");
62    list.append("1st");
63    list.append("2nd");
64    list.append("3rd");
65    list.append("tail");
66    let mut node = list.head();
67    loop {
68        println!("{}", node.borrow().data());
69        if node.borrow().next.is_none() {
70            break;
71        } else {
72            let next_item = node.borrow().next.as_ref().unwrap().clone();
73            node = next_item;
74        }
75    }
76    println!("====================");
77    let mut node = list.tail();
78    loop {
79        println!("{}", node.borrow().data());
80        if node.borrow().prev.is_none() {
81            break;
82        } else {
83            let prev_item = node.borrow().prev.as_ref().unwrap().clone();
84            node = prev_item;
85        }
86    }
87}
© 2025 青蛙小白 | 总访问量 | 总访客数