为什么有人想要使用链表而不是数组?

毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。

我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?

这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的Java类,而这个问题是关于一般数据结构的。


当前回答

使用链接列表的人必须阅读。人们会再次爱上数组的。 它谈到了 无序执行,硬件预取,内存延迟等。

http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html

其他回答

链表比数组的维护开销更大,它还需要额外的内存存储,所有这些都是一致的。但是有一些事情是数组做不到的。在很多情况下,假设你想要一个长度为10^9的数组你无法得到它,因为必须有一个连续的内存位置。链表可能是这里的救世主。

假设你想用数据存储多个东西,那么它们可以很容易地扩展到链表中。

STL容器通常在后台有链表实现。

没有人再编写自己的链表了。那太愚蠢了。使用链表需要更多代码的前提是错误的。

如今,构建链表只是学生们的一个练习,以便他们能够理解这个概念。相反,每个人都使用预先构建的列表。在c++中,根据我们问题中的描述,这可能意味着stl向量(#include <vector>)。

因此,选择链表还是数组完全是权衡每个结构相对于应用程序需求的不同特征。克服额外的编程负担应该对决策没有任何影响。

合并两个链表(特别是两个双链表)比合并两个数组快得多(假设合并是破坏性的)。前者取O(1),后者取O(n)。

编辑:澄清一下,我在这里指的是无序意义上的“合并”,而不是归并排序。也许"串联"这个词更合适。

为什么有人想要使用链表而不是数组?

这只是一个原因——如果你需要一个链表数据结构,而你所使用的编程语言不支持指针。

链表是一个动态的数据结构,因此它可以在运行时通过分配和释放内存来增长和收缩。所以不需要给出链表的初始大小。插入和删除节点非常容易。

2-链表的大小可以在运行时增加或减少,因此没有内存浪费。在数组的情况下,有很多内存浪费,比如如果我们声明一个大小为10的数组,只存储6个元素,那么4个元素的空间就浪费了。链表中不存在这样的问题,因为只有在需要时才分配内存。

3-数据结构,如堆栈和队列可以很容易地实现使用链表。