何时在数组/数组列表中使用链表？

Question

我使用了很多列表和数组,但我还没有遇到过这样一个场景,即如果不比链表更容易使用数组列表那么容易.我希望有人能给我一些关于链表明显更好的例子.

Answer 1

在以下情况下,链接列表优于数组:

1. 您需要从列表中进行恒定时间插入/删除(例如在时间可预测性非常关键的实时计算中)

2. 你不知道列表中有多少项.对于数组,如果数组变得太大,您可能需要重新声明和复制内存

3. 您不需要随机访问任何元素

4. 您希望能够在列表中间插入项目(例如优先级队列)

在以下情况下,阵列最好:

1. 您需要索引/随机访问元素

2. 你知道提前数组中的元素数量,这样你就可以为数组分配正确的内存量

3. 在按顺序迭代所有元素时需要速度.您可以在数组上使用指针数学来访问每个元素,而您需要根据链表中每个元素的指针查找节点,这可能会导致页面错误,从而导致性能下降.

4. 记忆是一个问题.填充数组占用的内存少于链表.数组中的每个元素都只是数据.每个链表节点都需要数据以及指向链表中其他元素的一个(或多个)指针.

数组列表(如.Net中的那些)为您提供了数组的好处,但为您动态分配资源,这样您就不必过多担心列表大小,并且您可以在任何索引处删除项目而无需任何努力或重新洗牌元素.性能方面,arraylists比原始数组慢.

Answer 2

数组具有O(1)随机访问权限,但是添加内容或从中删除内容非常昂贵.

链接列表在任何地方添加或删除项目以及迭代都非常便宜,但随机访问是O(n).

Answer 3

Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

ArrayLists适用于一次性写入多次读取或appender,但在前面或中间添加/删除时效果不佳.

Answer 4

要添加到其他答案,大多数数组列表实现在列表的末尾保留额外的容量,以便可以在O(1)时间内将新元素添加到列表的末尾.当超出数组列表的容量时,将在内部分配一个更大的新数组,并复制所有旧元素.通常,新阵列的大小是旧阵列的两倍.这意味着平均而言,在数组列表的末尾添加新元素是这些实现中的O(1)操作.因此,即使您事先不知道元素的数量,只要您在末尾添加元素,数组列表仍然可能比添加元素的链接列表更快.显然,在数组列表中的任意位置插入新元素仍然是O(n)操作.

即使访问是连续的,访问数组列表中的元素也比链表更快.这是因为数组元素存储在连续的内存中,可以轻松缓存.链接列表节点可能分散在许多不同的页面上.

如果您知道要在任意位置插入或删除项目,我建议仅使用链接列表.几乎所有其他内容的数组列表都会更快.

Answer 5

如果您需要在中间插入项目并且不想开始调整数组大小并转移内容,则会显示列表的优点.

你是对的,通常情况并非如此.我有一些非常具体的案例,但不是太多.

Answer 6

这完全取决于您在迭代时执行的操作类型，所有数据结构都在时间和内存之间进行权衡，并且根据我们的需求，我们应该选择正确的 DS。因此，在某些情况下，LinkedList 比数组更快，反之亦然。考虑数据结构的三个基本操作。

• 搜寻中

由于 array 是基于索引的数据结构，搜索 array.get(index) 将花费 O(1) 时间，而 linkedlist 不是索引 DS，因此您需要遍历到 index ，其中 index <=n ，n 是链表的大小，因此，当随机访问元素时，数组比链表更快。

问：那么这背后的美丽是什么？

由于数组是连续的内存块，因此在第一次访问时，它们的大块将被加载到缓存中，这使得访问数组的剩余元素相对较快，因为我们访问数组中的元素，引用局部性也会增加，因此捕获的次数也会减少未命中，缓存局部性是指缓存中的操作，因此与内存中相比执行速度要快得多，基本上在数组中，我们最大化了缓存中顺序元素访问的机会。虽然链接列表不一定位于连续的内存块中，但不能保证列表中顺序出现的项目实际上在内存中彼此靠近排列，这意味着更少的缓存命中，例如更多的缓存未命中，因为我们需要从内存中读取对于链表元素的每次访问，这会增加访问它们所需的时间并降低性能，因此如果我们进行更多随机访问操作（即搜索），数组将很快，如下所述。

• 插入

这在 LinkedList 中简单快捷，因为与数组相比，LinkedList（在 Java 中）的插入操作是 O(1) 操作，考虑数组已满的情况，如果数组已满，我们需要将内容复制到新数组，这使得插入一个在最坏的情况下，将元素放入 ArrayList 的时间复杂度为 O(n)，而 ArrayList 还需要更新其索引，如果您在除数组末尾之外的任何地方插入某些内容，在链表的情况下，我们不需要调整它的大小，您只需要更新指针。

• 删除

它的工作方式类似于插入，并且在 LinkedList 中比数组更好。