为什么SortedList和List使用数组，为什么LinkedList用得不多？
在我看来，List 基本上是使用 LinkedList 实现的，而普通的 Array 是作为连续块实现的。我总是使用 List 因为它位于 Generic 命名空间中，并且因为我认为它使用动态内存分配 - 但我错了。
昨天看到用Reflector实现List，发现其实是一个T(T[])数组。在操作 List 中的每个元素时，有很多 Array.Copy 。例如，当您使用Insert时，它将创建一个新的内存并复制插入元素之前/之后的所有元素。所以在我看来，使用 List 是非常昂贵的。
我也看到了 SortedList 。我不确定为什么 SortedList 也在其中实现了一个数组。您不认为 SortedList 使用数组会很糟糕吗，因为每次对 List 进行较小的操作时都需要对列表进行排序？
我还想知道为什么 List 如此受欢迎，大多数人都使用它而不是使用 LinkedList。仅仅是因为索引器的灵活性吗？
In my mind, List is basically implemented using LinkedList, while a normal Array is implemented as contiguous blocks. I always used List because it is in the Generic namespace and because I thought it used dynamic memory allocation - but I was wrong.
Yesterday I saw the implementation of List using Reflector and found it is actually an array of T(T[]). There are lots of Array.Copy around while manipulating each element in the List. For instance, when you use Insert, it will create a new memory and copy all the elements before/after the inserted elements. So it seem to me the use of List is very expensive.
I saw the SortedList as well. I am not sure why a SortedList also implements an array inside it. Don't you think SortedList would be horrible to use an array as you need to sort the list every time a minor manipulation to the List occurs?
I also wonder why List is so popular as most people use it rather than going for LinkedList. Is it only because of the flexibility of the indexer?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
在现实生活中，List 并不经常调用 Array.Copy，通常您只是将项目追加到数组中，而不是插入。这是列表的目的，与链接列表不同。您只应该选择一个合适的集合类。
如果插入项目经常使用链表。如果您主要添加项目并需要有效地迭代它们，请使用List。
In real life List doesn't call Array.Copy often, usually you just append items to array, not insert. It's a purpose of List, in contrast to a linked list. You just should to choose a proper collection class.
If you insert items often use linked list. If you mostly add items and need to iterate them effectively, use List.
如果您想要单一类型的内存中集合，其中：
那么
List可能是您的最佳选择。当 (2) 和 (3) 不适用时，LinkedList可能是更好的选择。If you want an in-memory collection of a single-type for which:
then
List<T>is probably your best choice.LinkedList<T>may be a better choice when (2) and (3) do not apply.因为大多数集合不需要经常插入到中间。但它们确实需要通过索引器直接访问。
Because most collections don't need insertions into the middle often. But they do need directly access via an indexer.
最大的原因是现代计算机设计。 CPU 缓存非常非常重要，因为 RAM 速度很慢。内存总线设计无法跟上 CPU 时钟速度的快速发展。让高频数字信号传播超过一英寸是非常困难的。
数组具有无与伦比的缓存性能，当您迭代它时，下一个元素很可能已经在缓存中。链表给出的可能性很低，当项目以低速率添加时，下一个项目基本上位于随机地址。这是昂贵的，它会停止处理器，等待 RAM 赶上。可以循环数百次。
The biggest reason is modern computer design. The CPU cache is very important because RAM is so slow. The memory bus design just couldn't keep up with the rapid advances in CPU clock speeds. Making a high frequency digital signal travel more than an inch is very difficult.
An array has unbeatable cache performance, it very likely that the next element is already in the cache when you iterate it. A linked list gives low odds that this is the case, the next item is essentially at a random address when items are added at a low rate. That's expensive, it stalls the processor, waiting for the RAM to catch up. Can be hundreds of cycles.