使用数组实现链表-优势和优势劣势 [英] 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" 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屋！