使用数组实现链表 - 优点 &缺点 [英] implement linked list using array - advantages & disadvantages

问题描述

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

I know how to implement linked list using array. For example we define a struct as follow:

struct Node{
    int data;
    int link;
}

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

"data" stores the info and "link" stores the index in the array of next node.

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

Can anybody tell me what is the advantage and disadvantage of implementing a linked list using array compared to "ordinary" linked list? Any suggestion will be appreciated.

推荐答案

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

If you back a linked list with an array, you'll end up with the disadvantages of both. Consequently, this is probably not a very good way to implement it.

一些直接的缺点:

1. 数组中的死空间(当前未用于项目的条目)会占用内存
2. 您必须跟踪免费条目 - 经过几次插入和删除操作后，这些免费条目可能位于任何地方.
3. 使用数组会对链表的大小施加上限.

我想一些优点是:

1. 如果您使用的是 64 位系统，您的指针"将占用更少的空间(尽管免费条目所需的额外空间可能超过了这一优势)
2. 您可以将数组序列化到磁盘，然后使用 mmap() 调用轻松地将其读回.不过，为了可移植性，您最好使用某种协议缓冲区.
3. 您可以保证数组中的元素在内存中彼此接近.

1. If you're on a 64 bit system, your "pointers" will take up less space (though the extra space required by free entries probably outweighs this advantage)
2. You could serialise the array to disk and read it back in with an mmap() call easily. Though, you'd be better off using some sort of protocol buffer for portability.
3. You could make some guarantees about elements in the array being close to each other in memory.

这篇关于使用数组实现链表 - 优点 &缺点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！