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

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

对我来说是这样的，

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.

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

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

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

为什么是链表而不是数组?有些人已经说过，插入和删除的速度更快。

但也许我们不需要生活在两者的限制下，同时获得两者的优点……是吗?

对于数组删除，您可以使用'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.

Eric Lippert最近发表了一篇关于数组应该保守使用的原因之一的文章。