本文介绍了使用数组实现链表-优势和优势劣势的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我知道如何使用数组实现链表.例如我们定义一个结构如下:
I know how to implement linked list using array. For examplewe define a struct as follow:
struct Node{
int data;
int 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.
一些直接的缺点:
- 您将在阵列中有死空间(当前未用于项的条目)占用内存
- 您必须跟踪免费条目-在几次插入和删除后,这些免费条目可能在任何地方.
- 使用数组将对链表的大小施加上限.
我想一些优点是:
- 如果您使用的是64位系统,则指针"将占用更少的空间(尽管免费条目所需的额外空间可能会超过此优势)
- 您可以将阵列序列化到磁盘,并通过
mmap()
调用轻松读回.不过,最好使用某种协议缓冲区来实现可移植性. - 您可以保证数组中的元素在内存中彼此靠近.
- 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)
- 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. - You could make some guarantees about elements in the array being close to each other in memory.
这篇关于使用数组实现链表-优势和优势劣势的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!