Rust中的链表

在 Rust 中学习链表相当麻烦，当你第一次看到像Option<Box<LinkedList>>这样的表达式时，简直是疯狂。我在这里写下了许多我不熟悉的内容！

概念#

在 Rust 中使用定义的链表的一种方式是Option<Box<LinkedList>>，其中使用两个包装器来确保 1）对象的可选存在，类似于 cpp 中的nullptr，以及 2）指向下一个元素的固定大小指针。

在 Rust 中操作 LinkedList 时会出现以下概念。通常，你可能想使用Option类型的as_mut()和take()方法来进行链表操作。

Mermaid Loading...

take的签名：

pub fn take(&mut self) -> Option(T)

take()用默认值（分别为None或Err）填充原始的Option对象或Result。这用于从其可变引用中获取可变Option()枚举的所有权。

要在这样的Option上创建可变引用，你可以使用在Option上实现的as_mut()特征，将&mut Option<T>转换为Option<&mut T>。签名如下：

fn as_mut(&mut self) -> &mut T;

通过这些魔法，我们终于可以在 cpp 中执行类似node1.next = node2; auto tmp = node2.next;的操作：

// 将指针更改为另一个
node2.as_mut()?.next = node1;
// 将当前节点的下一个移动到一个独立变量
let node3 = node2.as_mut()?.next.take();
// 移动对象本身很简单
node1 = node2;
node2 = node2;

为什么要使用`Box`？#

在 Rust 中，Box类型是用于在堆上分配数据的智能指针。当一个Box超出作用域时，它的析构函数会被调用，堆内存会被释放。

我们在LinkedList中的ListNode使用Box的原因是 Rust 的所有权和大小要求。在 Rust 中，所有变量和数据在编译时必须具有已知的大小。然而，LinkedList是一个递归数据结构，其中一个节点可以包含另一个节点。如果我们试图在没有Box的情况下定义它，它将具有无限大小，因为每个节点都包含另一个节点，依此类推。

通过使用Box，我们将ListNode存储在堆上，而不是直接存储在父节点中。这意味着父节点只需要存储Box，而Box具有已知的大小（它是指向堆内存的指针）。

ListNode可能如下所示：

pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

在这个定义中，每个ListNode包含一个可能包含指向下一个ListNode的Box的Option。Option用于指示next字段可能为None（可能没有下一个节点），而Box用于在堆上存储下一个ListNode。

因此，仅使用Option是不够的，因为它无法解决大小要求的问题。我们需要Box在堆上分配ListNode并为next字段提供已知的大小。

那么如何创建一个循环链表？#

Box是一个智能指针，或者更具体地说，是 cpp 中的唯一指针。这意味着在Box中创建的链表保证不会有循环，因为Box对它所指向的数据拥有独占所有权，防止对同一数据的多个可变引用，从而避免潜在的数据竞争。

在 Rust 中创建循环链表确实具有挑战性，因为 Rust 的所有权模型及其防止数据竞争的方式。然而，有一些方法可以在 Rust 中创建循环或更复杂的结构，但它们涉及使用Rc（引用计数）和RefCell类型。Rc允许同一数据的多个所有者，而RefCell允许内部可变性，这意味着即使有对其的不可变引用，我们也可以修改数据。

以下是如何创建循环的示例：

use std::rc::Rc;
use std::cell::RefCell;

struct Node {
    value: i32,
    next: Option<Rc<RefCell<Node>>>,
}

fn main() {
    let node1 = Rc::new(RefCell::new(Node { value: 1, next: None }));
    let node2 = Rc::new(RefCell::new(Node { value: 2, next: Some(node1.clone()) }));

    // 创建一个循环
    node1.borrow_mut().next = Some(node2.clone());
}

在这个例子中，node1指向node2，而node2又指向node1，形成一个循环。Rc类型允许两个节点互相拥有，而RefCell类型允许我们修改node1指向node2，即使node1最初是不可变的。

然而，这样的循环可能导致内存泄漏。在这个例子中，由于循环，node1和node2将永远不会被释放，因为它们的引用计数始终大于零。Rust 的Rc类型没有检测或处理循环的方式。

因此，虽然在 Rust 的LinkedList中创建循环是可能的，但如果不小心，可能会导致内存泄漏。

参考#

循环链表的实际用途？（来自 GPT4 的回答）#

是的，循环或圆形链表在现实应用中确实有实际用途。以下是一些示例：

轮转调度：这是一种在操作系统和其他处理时间共享的系统中使用的调度算法。任务列表保存在循环链表中，调度程序轮流处理任务，给每个任务一个小的执行时间片。当一个任务完成其轮次后，调度程序移动到循环列表中的下一个任务。
多人棋盘游戏：在许多多人游戏中，基于回合的系统可以通过循环链表实现。每个节点代表一个玩家，当前节点代表轮到的玩家。在每个回合之后，游戏向循环列表中的下一个玩家推进。
图像轮播或幻灯片：在网页或移动应用中，图像轮播或幻灯片可能使用循环链表来循环显示图像。当用户到达最后一张图像时，下一张图像是第一张，形成无缝循环。
CPU 缓存组织：在计算机架构中，一些缓存系统使用循环缓冲区（可以通过循环链表实现）来管理内存。
导航系统：一些导航系统使用循环链表来循环浏览选项或菜单。

虽然这些是实际用途，但值得注意的是，其他数据结构（如数组或数组列表）通常可以用于实现相同的目标，有时具有更好的性能特征。数据结构的选择取决于具体情况的要求。