Cons如何保存数据（Rust链表）

Question

我一直在学习 Rust，并决定做一些基本类型有助于更深入地学习这门语言。

Ln 4: // Cons: Tuple struct that wraps an element and a pointer to the next node

我认为这意味着它通过始终创建一个空节点来填充 Cons 来递归创建列表。

enum linkedList
{
    Head(Head), // Front Pointer and list metrics
    Cons(Arc<linkedList>, isize), //(Data, Next Value) Cons is apparently a LISP construct
    Tail(isize), // Rear Pointer
    Nil //Used to drop the stream
}

我真正的问题是允许数据存储在 Arc<linkedList> 节点中的底层机制是什么？我认为需要一个通用的 (<T>) 来将数据存储在列表中，但显然这是不正确的。

p.s 我的印象是 ARC 和 BOX 智能指针可以互换，但用于不同的目的。我试图制作一个单端翻转安全链表的线程安全版本，有点像循环队列。

Answer 1

您的实现与 Cons 列表的标准定义略有不同。直接的定义（类似于你在 Lisp 中的做法）是

type Data = isize;

enum List {
    Nil,
    Cons(Box<List>, Data),
}

如您所见，Cons 变体由嵌套列表和此节点数据元素组成。在您的情况下，每个节点都有一个 isize.

如果您有一个 Arc<List> 或 Box<List>，这个嵌套的 List 对象也可能是 Cons 变体并带有另一个 isize。 Arc 和 Box 不关心它们指向什么。

有些东西不是很地道。同时拥有 Tail 和 Nil 变体没有多大意义，因为现在您有两种方式来表示列表的结尾。同样，让 Head 成为列表的变体很奇怪，因为列表的头部仅在开头，但您的实现允许在列表中间使用 Head 变体。

最好不要有额外的 Nil 节点来表示列表的结尾。相反，最后一个节点知道它是最后一个（就像你的 Tail 变体），所以你没有为空节点额外分配。这就是我认为 Rust 中单链表的惯用定义：

struct List {
    // ...
    // extra info for list head
    // ...

    first_node: Option<Box<ListNode>>,
}

struct ListNode {
    value: Data,
    next: Option<Box<ListNode>>,
}

要使其成为泛型，我们只需删除之前的类型别名 Data 并将其改为泛型参数：

struct ListNode<T> {
    value: T,
    next: Option<Box<ListNode<T>>>,
}

关于Box和Arc：Box是指向堆上一个值的拥有指针，这意味着只有这个盒子拥有它指向的内存。 Arc 是 Rc 的线程安全版本，它是一个引用计数堆值。可以存在多个指向此内存的 Rc 指针并读取它，计算这些指针的数量。因此，所有权可以共享。

您应该根据是否要创建更多指向节点的引用计数指针来选择使用哪个（请注意，您可能希望 Rc<RefCell<Node>> 或 Arc<Mutex<Node>> 也发生变异创建后的列表）。如果您只有列表的头部并想对其进行迭代，请选择 Box。

Cons如何保存数据（Rust链表）

How does Cons save data (Rust Linked List)

data-structures

rust

linked-list

cons