为什么链表比数组更快？

Question

我对此非常困惑.到处都写着"链表比数组更快",但是没有人愿意说出为什么.使用普通逻辑我无法理解链表如何更快.在一个数组中,所有单元格彼此相邻,因此只要您知道每个单元格的大小,就可以立即轻松到达一个单元格.例如,如果有一个包含10个整数的列表,并且我想在第四个单元格中获取该值,那么我直接进入数组的开头+24个字节并从那里读取8个字节.

另一方面,如果你有一个链表并且你想要获得第四个元素,那么你必须从列表的开头或结尾开始(取决于它是单个列表还是双列表)并从一个节点开始到另一个,直到找到你想要的东西.

那么heck如何逐步进行比直接进入元素要快？

Answer 1

这个题目标题具有误导性.

它声称,链表是没有限制的范围以及比数组更快.有很多次,当数组可以明显更快时,链接列表可以显着更快的次数:链表"特别快"的特殊情况似乎不受支持.

有两件事需要考虑:

1. 特定操作中链表与数组的理论界限; 和
2. 实际的实现和使用模式,包括缓存局部性和分配.

就索引元素的访问而言:操作O(1)在数组中并且如指出的那样,非常快(只是一个偏移量).该操作是O(k)在一个链表(其中k是索引,并且可以总是<< n取决于)但如果在链接列表已经被遍历,那么这是O(1)每步是"相同"作为阵列.如果数组traversal(for(i=0;i<len;i++)更快(或更慢)取决于特定的实现/语言/运行时.

但是,如果存在特定情况,其中阵列对于上述任一操作(搜索或遍历)都不是更快,那么看到更详细地解剖将是有趣的.(我确信有可能在列表中找到一种非常简并的数组实现的语言咳嗽 Haskell 咳嗽)

快乐的编码.

我的简单用法摘要:数组适用于索引访问和涉及交换元素的操作.然而,非摊销的重新规模操作和额外的松弛(如果需要)可能相当昂贵.链接列表可以分摊重新调整大小(以及每个单元格的"指针"的交易松弛),并且通常可以在"切出或插入一堆元素"等操作中表现出色.最后,它们是不同的数据结构,应该这样对待.

Answer 2

像编程最多的问题,背景是一切.您需要考虑数据的预期访问模式,然后适当地设计存储系统.如果您插入一次,然后访问它1,000,000次,那么谁在乎插入成本是多少？另一方面,如果您在阅读时经常插入/删除,那么这些成本就会决定.

Answer 3

取决于您所指的操作。在链表中添加或删除元素比在数组中快得多。

在链表和数组中，一个接一个地顺序迭代的速度或多或少是相同的。

在数组中将一个特定元素放在中间要快得多。

并且数组可能会浪费空间，因为通常在扩展数组时，分配的元素多于当时所需的元素（想想 Java 中的 ArrayList）。

所以你需要根据你想要做什么来选择你的数据结构：

多次插入和顺序迭代 --> 使用 LinkedList

随机访问，理想情况下是预定义的大小 --> 使用数组

Answer 4

在以下情况下，链表优于数组：

a）您需要从列表中进行恒定时间的插入/删除（例如在实时计算中，时间可预测性绝对至关重要）

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

c) 你不需要随机访问任何元素

d) 您希望能够在列表中间插入项目（例如优先级队列）

在以下情况下，数组更可取：

a）您需要对元素进行索引/随机访问

b) 您提前知道数组中元素的数量，以便为数组分配正确的内存量

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

d) 记忆力是一个问题。填充数组比链表占用更少的内存。数组中的每个元素只是数据。每个链表节点都需要数据以及一个（或多个）指向链表中其他元素的指针。

数组列表（如 .Net 中的数组列表）为您提供了数组的优点，但为您动态分配资源，这样您就不必过多担心列表大小，并且可以删除任何索引处的项目，无需任何努力或重新创建。洗牌元素。从性能角度来看，数组列表比原始数组慢。

参考：拉马尔回答 /sf/answers/27550491/

Answer 5

因为在数组中间插入时不会移动内存。对于您提出的情况，它是正确的 - 数组更快，您只需要算术即可从一个元素转到另一个元素。链表需要间接寻址和片段内存。关键是要知道使用什么结构以及何时使用。