c# - 为什么 SortedList 和 List 使用数组，为什么 LinkedList 用得不多？

Question

在我看来，List 基本上是使用 LinkedList 实现的，而普通的 Array 是作为连续 block 实现的。我一直使用 List，因为它位于 Generic 命名空间中，而且我认为它使用了动态内存分配 - 但我错了。

昨天看到用Reflector实现List，发现其实是一个T(T[])的数组。在操作 List 中的每个元素时，周围有很多 Array.Copy。例如，当您使用 Insert 时，它会创建一个新内存并复制插入元素之前/之后的所有元素。所以在我看来，List 的使用非常昂贵。

我也看到了 SortedList。我不确定为什么 SortedList 也在其中实现了一个数组。您不认为 SortedList 使用数组会很糟糕吗，因为每次对 List 进行较小的操作时您都需要对列表进行排序？

我也想知道为什么 List 如此受欢迎，因为大多数人都使用它而不是使用 LinkedList。仅仅是因为索引器的灵 active 吗？

Answer 1

最大的原因是现代计算机设计。 CPU 缓存非常很重要，因为 RAM 太慢了。内存总线设计跟不上 CPU 时钟速度的快速发展。让高频数字信号传播超过一英寸是非常困难的。

数组具有无可匹敌的缓存性能，当你迭代它时，很可能下一个元素已经在缓存中了。链表给出这种情况的可能性很小，当以低速率添加项目时，下一个项目基本上位于随机地址。这很昂贵，它会使处理器停顿，等待 RAM catch 来。可以是数百个周期。