在C#中实现List <T>？

Question

首先,我很抱歉我的英语不好,然后我的问题;

我知道有很多这样的问题,在这里,但我找不到直接的答案.正在List<T>使用某种形式的"链表"机制来实现？或者它只是一个过度设计的阵列？

我对列表的性能问题很感兴趣,比如排序,插入和删除项目.例如,对于插入操作,"链表"只定义了一些新连接,但数组需要移动其值.列表怎么样？

Answer 1

是的,List <>是一个数组.是的,Insert()是一个O(n)操作.

重要的是它以这种方式工作,现代处理器非常依赖于它们的缓存.机器中的RAM 非常慢,比处理器慢得多.缓存可以快速顺序访问内存.这与LinkedList <>的作用相反.单个缓存未命中需要花费数百个cpu周期.请注意LinkedList <>的另一个显着缺点,索引它的成本为O(n),除非您可以按顺序索引.列表总是O(1).

这些只是粗略的指导原则,没有人可以建议您用LinkedList替换List.只有剖析器才能做到这一点.