While many of you have touched upon major adv./dis of linked list vs array, most of the comparisons are how one is better/ worse than the other.Eg. you can do random access in array but not possible in linked list and others. However, this is assuming link lists and array are going to be applied in a similar application. However a correct answer should be how link list would be preferred over array and vice-versa in a particular application deployment. Suppose you want to implement a dictionary application, what would you use ? Array : mmm it would allow easy retrieval through binary search and other search algo .. but lets think how link list can be better..Say you want to search "Blob" in dictionary. Would it make sense to have a link list of A->B->C->D---->Z and then each list element also pointing to an array or another list of all words starting with that letter ..

A -> B -> C -> ...Z
|    |    |
|    |    [Cat, Cave]
|    [Banana, Blob]
[Adam, Apple]

Now is the above approach better or a flat array of [Adam,Apple,Banana,Blob,Cat,Cave] ? Would it even be possible with array ? So a major advantage of link list is you can have an element not just pointing to the next element but also to some other link list/array/ heap/ or any other memory location. Array is a one flat contigous memory sliced into blocks size of the element it is going to store.. Link list on the other hand is a chunks of non-contigous memory units (can be any size and can store anything) and pointing to each other the way you want. Similarly lets say you are making a USB drive. Now would you like files to be saved as any array or as a link list ? I think you get the idea what I am pointing to :)

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

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

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

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

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

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

假设您有一个有序集，您还想通过添加和删除元素来修改它。此外，您需要能够以这样的方式保留对元素的引用，以便稍后可以获得前一个或下一个元素。例如，一本书中的待办事项列表或一组段落。

首先，我们应该注意到，如果您想在集合本身之外保留对对象的引用，那么您可能最终会将指针存储在数组中，而不是存储对象本身。否则你将无法插入到数组中-如果对象嵌入到数组中，它们将在插入期间移动，并且任何指向它们的指针都将无效。数组下标也是如此。

您的第一个问题，正如您自己所注意到的，是插入链表允许插入O(1)，但数组通常需要O(n)。这个问题可以部分克服——可以创建一种数据结构，提供类似数组的按顺序访问接口，其中读和写在最坏的情况下都是对数的。

Your second, and more severe problem is that given an element finding next element is O(n). If the set was not modified you could retain the index of the element as the reference instead of the pointer thus making find-next an O(1) operation, but as it is all you have is a pointer to the object itself and no way to determine its current index in the array other than by scanning the entire "array". This is an insurmountable problem for arrays - even if you can optimized insertions, there is nothing you can do to optimize find-next type operation.

这实际上是一个效率问题，在链表中插入、删除或移动(而不是简单地交换)元素的开销是最小的，即操作本身是O(1)，而不是O(n)。如果您大量操作数据列表，这可能会产生显著的差异。您可以根据对数据类型的操作方式选择数据类型，并为所使用的算法选择最有效的数据类型。

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

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