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

Question

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

struct Node{
    int data;
    int link;
}

"data"存储信息,"link"将索引存储在下一个节点的数组中.

谁能告诉我使用数组实现链表与"普通"链表相比有什么优缺点？任何建议将不胜感激.

Answer 1

如果您使用数组备份链接列表,则最终会遇到两者的缺点.因此,这可能不是实现它的好方法.

一些直接的缺点:

1. 占用内存时,数组中的死空间(当前不用于项目的条目)将占用空间
2. 您必须跟踪免费条目 - 在几次插入和删除后,这些免费条目可以在任何地方.
3. 使用数组将对链表的大小施加上限.

我想一些优点是:

1. 如果您使用的是64位系统,那么"指针"将占用更少的空间(尽管自由条目所需的额外空间可能超过此优势)
2. 您可以将阵列序列化为磁盘并mmap()轻松地通过呼叫将其读回.但是,您最好使用某种协议缓冲区来实现可移植性.
3. 您可以保证数组中的元素在内存中彼此接近.