arrays - 为什么链表比数组快？

Question

我对此感到非常困惑。到处都写着“链表比数组快”，但没有人努力说出为什么。使用简单的逻辑我无法理解链接列表如何更快。在阵列中，所有单元格都彼此相邻，因此只要您知道每个单元格的大小，就很容易立即到达一个单元格。例如，如果有一个包含 10 个整数的列表，并且我想获取第四个单元格中的值，那么我只需直接转到数组的开头 + 24 个字节并从那里读取 8 个字节。

另一方面，当您有一个链表并且想要将元素放在第四位时，您必须从列表的开头或结尾(取决于它是单列表还是双列表)并从一个节点开始到另一个，直到你找到你要找的东西。

那么，如何一步一步地比直接进入一个元素更快呢？

Answer 1

这个问题标题具有误导性。

它断言链表比数组更快，而没有很好地限制范围。有很多时候数组可以明显更快，也有很多时候链表可以明显更快:似乎不支持链接列表“更快”的特殊情况。

有两件事需要考虑:

特定操作中链表与数组的理论界限；和

现实世界的实现和使用模式，包括缓存局部性和分配。

至于索引元素的访问:操作是O(1)在数组中 正如所指出的，速度非常快(只是一个偏移量)。 操作是O(k)在链表中 (其中 k 是索引，可能总是 << n ，具体取决于)但如果链表已经被遍历，那么这是 O(1)每个步骤与数组“相同”。如果数组遍历( for(i=0;i<len;i++ )更快(或更慢)取决于特定的实现/语言/运行时。

但是，如果存在特定情况下，对于上述任一操作(查找或遍历)，数组都不是更快，那么更详细地剖析会很有趣。 (我相信有可能找到一种语言，它在列表上有非常退化的数组实现咳 haskell 咳)

快乐编码。

我的简单用法总结:数组适用于涉及交换元素的索引访问和操作。然而，未摊销的重新调整大小操作和额外的松弛(如果需要)可能会相当昂贵。链表可以分摊重新调整大小(并为每个单元格的“指针”交换冗余)，并且通常可以在诸如“切出或插入一堆元素”之类的操作中表现出色。最后，它们是不同的数据结构，应该这样对待。