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

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

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

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


当前回答

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

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

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

其他回答

对我来说是这样的,

Access Linked Lists allow only sequential access to elements. Thus the algorithmic complexities is order of O(n) Arrays allow random access to its elements and thus the complexity is order of O(1) Storage Linked lists require an extra storage for references. This makes them impractical for lists of small data items such as characters or boolean values. Arrays do not need an extra storage to point to next data item. Each element can be accessed via indexes. Size The size of Linked lists are dynamic by nature. The size of array is restricted to declaration. Insertion/Deletion Elements can be inserted and deleted in linked lists indefinitely. Insertion/Deletion of values in arrays are very expensive. It requires memory reallocation.

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

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

除了插入到列表中间更容易之外——从链表中间删除也比从数组中删除容易得多。

但坦率地说,我从未使用过链表。每当我需要快速插入和删除时,我也需要快速查找,所以我使用HashSet或Dictionary。

除了在列表中间进行添加和删除之外,我更喜欢链表,因为它们可以动态地增长和收缩。

这里有一个快速的方法:移除物品更快。