Chainlink

另一个链表？

Chainlink提供由生成式内存分配器支持的单向和双向链表。通过使用生成式内存分配器，我们可以完全避免不安全代码（chainlink是 #[deny(unsafe)]），并且可以通过消除指针追逐来提高缓存局部性。一切都被连续存储。

这就是为什么它被称为"chainlink"。在真实的链链栅栏中，链接是连续的。此外，这个名称在crates.io上也是可用的。

限制

大小

因为我们使用的是生成式内存分配器的索引而不是指针，所以在链表中的内部链接将使用更多的内存，其他条件相同。生成式内存分配器的索引必然需要存储指针等效物——这里只是一个 usize，其大小与指针相同——以及一个代数号。

我们已经为默认链表选择了不同的权衡。索引的大小与指针相同，但可以容纳的元素更少。这意味着我们的默认列表可以容纳40亿（实际上是2^32 - 1）个元素，每个元素最多可以更新40亿次。

对于大多数应用程序来说，这可能是合理的限制。然而，如果您觉得可能会接近这些限制中的任何一个，我们提供了具有更大的向量偏移和代数的备用实现。

追加

因为 std 的链表使用共享的通用分配器，所以不同链表的节点可以连接到一起，而无需重新分配和复制。这使得用户可以创建两个任意大小的独立列表，并以常量和常数时间将它们追加。

Chainlink目前无法有效地执行相同的操作。如果我们把链表B中的所有节点移动到链表A中，这将花费与链表B中元素数量成比例的时间。