猿问
下载APP

数组与链表

为什么有人想在阵列上使用链表?


毫无疑问,对链接列表进行编码比使用数组要多一些工作,人们可能想知道什么是合理的额外工作。


我认为在链表中插入新元素是微不足道的,但它是数组中的一项重要工作。使用链表存储一组数据与将其存储在数组中是否还有其他优点?


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


DIEA
浏览 42回答 3
3回答

繁花不似锦

在链表中存储不同大小的数据更容易。数组假定每个元素的大小完全相同。正如您所提到的,链表更容易有机增长。数组的大小需要提前知道,或者在需要增长时重新创建。改组链表只是改变指向什么的问题。混乱阵列更复杂和/或占用更多内存。只要您的迭代都发生在“foreach”上下文中,您就不会在迭代中失去任何性能。

慕少森

另一个很好的理由是链表很适合高效的多线程实现。这样做的原因是更改往往是本地的 - 只影响一个或两个指针,以便在数据结构的本地化部分插入和删除。因此,您可以让许多线程在同一个链表上工作。更重要的是,可以使用CAS类型的操作创建无锁版本,并完全避免重量级锁定。使用链表,迭代器也可以在发生修改时遍历列表。在乐观的情况下,修改不会发生冲突,迭代器可以继续而不会发生争用。使用数组,任何修改数组大小的更改都可能需要锁定数组的大部分内容,事实上,如果没有跨整个数组的全局锁定就很少这样做,因此修改就会阻止这个世界事务。

米脂

维基百科有很好的部分关于差异。链接列表与数组相比有几个优点。元素可以无限期地插入到链表中,而数组最终会填满或需要调整大小,这是一项昂贵的操作,如果内存碎片化甚至可能无法实现。类似地,从中移除许多元素的阵列可能变得浪费空或者需要变小。另一方面,数组允许随机访问,而链表仅允许对元素进行顺序访问。事实上,单链表只能在一个方向上进行。这使链接列表不适合于快速查找元素的应用程序,例如heapsort。由于引用和数据高速缓存的位置,对阵列的顺序访问也比许多机器上的链接列表更快。链接列表几乎没有从缓存中获益。链表的另一个缺点是引用所需的额外存储空间,这通常使得它们对于诸如字符或布尔值的小数据项列表而言是不实际的。它也可能很慢,并且对于每个新元素分别为每个新元素分配内存而浪费一个天真的分配器,通常使用内存池解决问题。http://en.wikipedia.org/wiki/Linked_list
打开App,查看更多内容
随时随地看视频慕课网APP
我要回答