为什么有人想要使用链表而不是数组?
毫无疑问，编码一个链表比使用数组要多一些工作，人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的，但在数组中这是一个主要的任务。与将数据存储在数组中相比，使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复，因为另一个问题是专门问一个特定的Java类，而这个问题是关于一般数据结构的。
当前回答
为什么是链表而不是数组?有些人已经说过，插入和删除的速度更快。
但也许我们不需要生活在两者的限制下，同时获得两者的优点……是吗?
对于数组删除，您可以使用'Deleted'字节来表示一行已被删除的事实，因此不再需要重新组织数组。为了减轻插入或快速更改数据的负担，可以使用链表。然后，在引用它们的时候，让你的逻辑先搜索一个，再搜索另一个。因此，将它们结合使用可以使您获得两者的最佳效果。
If you have a really large array, you could combine it with another, much smaller array or linked list where the smaller one hold thes 20, 50, 100 most recently used items. If the one needed is not in the shorter linked list or array, you go to the large array. If found there, you can then add it to the smaller linked list/array on the presumption that 'things most recently used are most likey to be re-used' ( and yes, possibly bumping the least recently used item from the list ). Which is true in many cases and solved a problem I had to tackle in an .ASP security permissions checking module, with ease, elegance, and impressive speed.
其他回答
除了插入到列表中间更容易之外——从链表中间删除也比从数组中删除容易得多。
但坦率地说，我从未使用过链表。每当我需要快速插入和删除时，我也需要快速查找，所以我使用HashSet或Dictionary。
除了在列表中间进行添加和删除之外，我更喜欢链表，因为它们可以动态地增长和收缩。
Eric Lippert最近发表了一篇关于数组应该保守使用的原因之一的文章。
A widely unappreciated argument for ArrayList and against LinkedList is that LinkedLists are uncomfortable while debugging. The time spent by maintenance developers to understand the program, e.g. to find bugs, increases and IMHO does sometimes not justify the nanoseconds in performance improvements or bytes in memory consumption in enterprise applicatons. Sometimes (well, of course it depends on the type of applications), it's better to waste a few bytes but have an application which is more maintainable or easier to understand.
例如，在Java环境中，使用Eclipse调试器，调试ArrayList将显示一个非常容易理解的结构:
arrayList ArrayList<String>
elementData Object[]
[0] Object "Foo"
[1] Object "Foo"
[2] Object "Foo"
[3] Object "Foo"
[4] Object "Foo"
...
另一方面，查看LinkedList的内容并找到特定的对象变成了一个展开树的噩梦，更不用说过滤LinkedList内部信息所需的认知开销:
linkedList LinkedList<String>
header LinkedList$Entry<E>
element E
next LinkedList$Entry<E>
element E "Foo"
next LinkedList$Entry<E>
element E "Foo"
next LinkedList$Entry<E>
element E "Foo"
next LinkedList$Entry<E>
previous LinkedList$Entry<E>
...
previous LinkedList$Entry<E>
previous LinkedList$Entry<E>
previous LinkedList$Entry<E>
使用链接列表的人必须阅读。人们会再次爱上数组的。 它谈到了 无序执行，硬件预取，内存延迟等。
http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html
