List<T>和LinkedList<T>之间的差异

好, List<T> 基本上是由一个数组支持的,这个数组通常大于当前的项目数。元素被放入一个数组中,当旧的数组用完空间时创建一个新的数组。这对于按索引进行访问很快,但对于在列表中或开始时删除或插入元素则很慢。在列表末尾添加/删除条目相当便宜。

LinkedList<T> 是一个双链接列表-每个节点都知道其上一个条目和下一个条目。这对于在特定节点(或头部/尾部)之后/之前插入是很快的,但对于按索引访问则很慢。

链接列表; 将 通常 占用的内存比 列表<T> 因为它需要空间来容纳所有下一个/上一个引用,而且数据可能具有较少的引用局部性,因为每个节点都是一个单独的对象。另一方面,一个 列表<T> 可以 有一个比当前需要大得多的后备阵列。

一个 List<T> 实际上是一个数组,意思是 Add 操作是O(1)在末尾,O(n)在前面,但是您可以在O(1)中索引到它。一个 LinkedList<T> 就像上面说的,是一个链表。因为它是双链接的,所以可以在O(1)中添加前面或后面的项目,但是索引为O(n)。

在几乎所有情况下,一个列表的性能都会超过一个LinkedList。现实世界的结果往往与大O复杂理论不同。