首先我很抱歉我的英语不好，然后是我的问题；
我知道有很多这样的问题，在这里，但我没有找到一个直接的答案。是List<T>使用某种“链表”机制实现的吗？或者它只是一个过度设计的阵列？
我对列表的性能问题感兴趣，例如排序、插入和删除项目。例如对于插入操作，“链表”只是定义了一些新的连接，但数组需要改变它的值。清单呢？
问问题
807 次
4 回答
6
是的， List<> 是一个数组。是的，Insert() 是一个 O(n) 操作。
以这种方式工作很重要，现代处理器非常依赖于它们的缓存。您机器中的 RAM非常慢，比处理器慢得多。高速缓存可以快速顺序访问内存。这与 LinkedList<> 的作用相反。单个缓存未命中会花费数百个 cpu 周期。请注意 LinkedList<> 的另一个显着缺点，除非您可以按顺序索引，否则索引它的成本为 O(n)。List 总是 O(1)。
这些只是粗略的指导方针，没有人可以建议您用 LinkedList 替换您的列表。只有分析器才能做到这一点。
于 2013-07-28T03:08:10.593 回答
3
我会说这只是一个过度设计的阵列。对于链接列表，您需要LinkedList<T>. 有关LinkedList<T>阅读此内容的更多信息
于 2013-07-28T02:57:21.310 回答
2
我会考虑List<T>过度设计的数组，而不是“链表”。
至于性能，由于List<T>不是固有排序的，因此性能取决于排序算法（冒泡排序非常慢，因为每个项目都需要检查）。
在 a 中插入和删除项目非常简单，使用vs.List<T>可以提高插入项目的性能，并将其添加到列表的末尾。List<T>.Add()List<T>.Insert().Add()
要全面了解各种 .NET 集合类型的性能和一般用例，请阅读C#/.NET 基础知识：选择正确的集合类
于 2013-07-28T03:10:20.723 回答
2
不，List 不是链表，它只是一个方便的强类型数组。我不会把它称为工程数组，但它是从 C# 2.0 引入的最佳特性之一。如果通用列表的性能是一个问题，则可以根据用例对其进行优化，但即使在巨大的列表中插入也不会花费太多时间。
于 2013-07-28T04:28:25.123 回答