数组与链表 [英] Array versus linked-list

问题描述

为什么有人要在数组上使用链表?

Why would someone want to use a linked-list over an array?

毫无疑问，编写链表比使用数组要多一些工作，人们可能想知道什么值得付出额外的努力.

Coding a linked-list is, no doubt, a bit more work than using an array and one may wonder what would justify the additional effort.

我认为在链表中插入新元素是微不足道的，但在数组中却是一件大事.与将数据存储在数组中相比，使用链表存储一组数据还有其他优势吗?

I think insertion of new elements is trivial in a linked-list but it's a major chore in an array. Are there other advantages to using a linked list to store a set of data versus storing it in an array?

这个问题不是这个问题的重复，因为另一个问题是专门询问特定的 Java 类，而这个问题与一般数据结构有关.

This question is not a duplicate of this question because the other question is asking specifically about a particular Java class while this question is concerned with the general data structures.

推荐答案

另一个很好的理由是链表非常适合高效的多线程实现.这样做的原因是更改往往是局部的——只影响一两个指针，用于在数据结构的局部部分插入和删除.因此，您可以让多个线程处理同一个链表.更重要的是，可以使用 CAS 类型的操作创建无锁版本并完全避免重量级锁.

Another good reason is that linked lists lend themselves nicely to efficient multi-threaded implementations. The reason for this is that changes tend to be local - affecting only a pointer or two for insert and remove at a localized part of the data structure. So, you can have many threads working on the same linked list. Even more, it's possible to create lock-free versions using CAS-type operations and avoid heavy-weight locks altogether.

对于链表，迭代器也可以在发生修改时遍历链表.在修改不冲突的乐观情况下，迭代器可以继续而不会发生争用.

With a linked list, iterators can also traverse the list while modifications are occurring. In the optimistic case where modifications don't collide, iterators can continue without contention.

对于数组，任何修改数组大小的更改都可能需要锁定数组的很大一部分，事实上，很少在没有全局锁定整个数组的情况下完成此操作，因此修改变得停止世界事务.

With an array, any change that modifies the size of the array is likely to require locking a large portion of the array and in fact, it's rare that this is done without a global lock across the whole array so modifications become stop the world affairs.

这篇关于数组与链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！