data-structures - 使用数组实现链表 - 优点和缺点

Question

我知道如何使用数组实现链表。例如
我们定义一个结构如下:

struct Node{
    int data;
    int link;
}

“数据”存储信息，“链接”存储下一个节点数组中的索引。

谁能告诉我与“普通”链表相比，使用数组实现链表的优缺点是什么？任何建议将不胜感激。

Answer 1

如果你用一个数组来支持一个链表，你最终会遇到 的缺点。 .因此，这可能不是实现它的好方法。

一些直接的缺点:

数组中的死空间(当前未用于项目的条目)将占用内存

您必须跟踪免费条目 - 经过几次插入和删除后，这些免费条目可能在任何地方。

使用数组将对链表的大小施加上限。

我想一些优点是:

如果您使用的是 64 位系统，您的“指针”将占用更少的空间(尽管免费条目所需的额外空间可能超过了这个优势)

您可以将数组序列化到磁盘并使用 mmap() 读回它。轻松调用。不过，为了可移植性，您最好使用某种 Protocol Buffer 。

您可以保证数组中的元素在内存中彼此接近。