何时应该使用List而不是LinkedList?
将链式列表视为列表可能会有些误导。它更像是一个链条。事实上,在 .NET 中,LinkedList
甚至没有实现 IList
接口。链表中没有真正的索引概念,尽管可能看起来有。该类提供的所有方法都不接受索引。
链表可以是单向的,也可以是双向的。这指的是链中每个元素仅具有到下一个元素的链接(单向链接),还是同时具有到前/后元素的链接(双向链接)。LinkedList
是双向链接的。
在内部,List
是由一个数组支持的。这提供了一个在内存中非常紧凑的表示。相反,LinkedList
需要额外的内存来存储相邻元素之间的双向链接。因此,LinkedList
的内存占用将普遍比 List
大(但有一个警告:为了在追加操作期间提高性能,List
可能具有未使用的内部数组元素。)
它们也具有不同的性能特征:
追加
LinkedList
常数时间.AddLast(item) List
平摊常数时间,线性最坏情况.Add(item)
前置
LinkedList
常数时间.AddFirst(item) List
线性时间.Insert(0, item)
插入
LinkedList
常数时间.AddBefore(node, item) LinkedList
常数时间.AddAfter(node, item) List
线性时间.Insert(index, item)
删除
LinkedList
线性时间.Remove(item) LinkedList
常数时间.Remove(node) List
线性时间.Remove(item) List
线性时间.RemoveAt(index)
数量
LinkedList
常数时间.Count List
常数时间.Count
包含
LinkedList
线性时间.Contains(item) List
线性时间.Contains(item)
清除
LinkedList
线性时间.Clear() List
线性时间.Clear()
从以上内容可以看出,它们基本上是等效的。在实践中,LinkedList
的 API 使用起来更为麻烦,并且其内部需要的细节会泄漏到您的代码中。
然而,如果你需要频繁地在列表内进行插入或删除,它可以提供恒定的时间。而List
则需要线性时间,因为在插入或删除后必须对列表中多余的项目进行调整。