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

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

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

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


当前回答

另一个很好的原因是链表非常适合高效的多线程实现。这样做的原因是,更改往往是局部的——只影响数据结构局部部分的插入和删除的一两个指针。所以,你可以让多个线程在同一个链表上工作。更重要的是,可以使用cas类型的操作创建无锁版本,并完全避免沉重的锁。

使用链表,迭代器还可以在进行修改时遍历列表。在修改没有冲突的乐观情况下,迭代器可以在没有争用的情况下继续。

对于数组,任何修改数组大小的更改都可能需要锁定数组的很大一部分,事实上,这是在整个数组上没有全局锁的情况下完成的,因此修改会停止全局事务。

其他回答

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

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

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

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

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

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 :)

根据你的语言,可以考虑以下一些缺点和优点:

C编程语言:当使用链表(通常是通过结构指针)时,必须特别注意不要泄漏内存。正如前面提到的,链表很容易洗牌,因为我们所做的只是改变指针,但是我们会记得释放所有的东西吗?

Java: Java具有自动垃圾收集功能,因此内存泄漏不会成为问题,但是对于高级程序员来说,隐藏了链表的实现细节。从列表中间删除节点等方法的过程比该语言的一些用户所期望的要复杂得多。