Cons如何保存数据(Rust链表)

Question

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

"；Rust by Example"；链接列表页面状态

Ln 4://缺点：封装一个元素和指向下一个节点的指针的元组结构

我认为这意味着它总是通过创建一个空节点来填充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变体放在列表的中间。

优选的是不具有额外的CCD_ 17节点来用信号通知列表的结束。相反，最后一个节点知道它是最后一个(就像您的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。