在我看来,List
基本上是使用 LinkedList
实现的,而普通的 Array
是作为连续 block 实现的。我一直使用 List
,因为它位于 Generic
命名空间中,而且我认为它使用了动态内存分配 - 但我错了。
昨天看到用Reflector实现List
,发现其实是一个T(T[]
)的数组。在操作 List
中的每个元素时,周围有很多 Array.Copy
。例如,当您使用 Insert
时,它会创建一个新内存并复制插入元素之前/之后的所有元素。所以在我看来,List
的使用非常昂贵。
我也看到了 SortedList
。我不确定为什么 SortedList
也在其中实现了一个数组。您不认为 SortedList
使用数组会很糟糕吗,因为每次对 List
进行较小的操作时您都需要对列表进行排序?
我也想知道为什么 List
如此受欢迎,因为大多数人都使用它而不是使用 LinkedList
。仅仅是因为索引器的灵 active 吗?
最佳答案
最大的原因是现代计算机设计。 CPU 缓存非常很重要,因为 RAM 太慢了。内存总线设计跟不上 CPU 时钟速度的快速发展。让高频数字信号传播超过一英寸是非常困难的。
数组具有无可匹敌的缓存性能,当你迭代它时,很可能下一个元素已经在缓存中了。链表给出这种情况的可能性很小,当以低速率添加项目时,下一个项目基本上位于随机地址。这很昂贵,它会使处理器停顿,等待 RAM catch 来。可以是数百个周期。
关于c# - 为什么 SortedList 和 List 使用数组,为什么 LinkedList 用得不多?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3703695/