我需要一种数据结构,它可以保存相同类型的元素列表。所需功能包括:
- 添加
- GetEnumerator(获取枚举器)
- (可能) 清除
索引访问、排序、搜索、删除元素不是必需的。最适合此要求的集合类是什么?应该考虑以下几个方面:性能、内存使用情况和垃圾回收器的行为。
我目前的候选对象是List<T>
和LinkedList<T>
我需要一种数据结构,它可以保存相同类型的元素列表。所需功能包括:
索引访问、排序、搜索、删除元素不是必需的。最适合此要求的集合类是什么?应该考虑以下几个方面:性能、内存使用情况和垃圾回收器的行为。
我目前的候选对象是List<T>
和LinkedList<T>
除非你处理的是一个庞大的结构或者你计划迭代这个东西一万亿次,否则它并不重要。只需选择其中之一,开始编码。如果您的应用程序稍后变得缓慢,请找出其原因并根据需要进行更改。
(说真的,它并.不.重要。你花费在寻找这个问题答案的每一分钟都是离有可工作的代码更近的一分钟)。
如果有人到达了必须知道区别的地步,LinkedList比List更快,并且仅需要非随机、只能向前读取和添加功能时可以使用。
简短回答
在几乎所有情况下,应该默认使用List<T>
。
稍长的回答
只有当您需要频繁添加和删除值时,且列表的大小较大时,LinkedList<T>
才会更好。如果在分析后发现使用 List<T>
会出现问题,则这只应该是您选择的一个因素。
更长的回答
假设您已经确定了使用其中一种的性能问题。
List<T>
的速度都会更快。List<T>
几乎总是更快的。LinkedList<T>
。确定哪些值/用法转换为更好的性能非常依赖于您的用法配置文件。微基准测试在这里可能非常误导,因为它们掩盖了链表行为的某些方面,例如节点在内存中分布而不是像在测试中一样被分配在一起。同样,使用正确大小预先创建 List<T>
可以产生很大的差异。
至于计算机科学风格的推理和大 O 表示法(在本例中真正需要大 N 才有意义)
List<T>
成本LinkedList<T>
成本LinkedList<T>
实现是双向链接的)内存使用是很复杂的,因为List在任何时候最多可以有Count-1个额外的单元,但LinkedList<T>将为每个单元消耗一个LinkedListNode<T>,这是额外的3个引用(每个引用4/8字节)加上通常的对象开销。在正常使用中,List可能会获胜,但如果您发现内存消耗实际上是一个问题,那么这只应该是您担心的事情。
Clear
。两者的时间复杂度均为 O(n)。 - nawfalList<T>
,因为如果数据是值类型,它们将按顺序存储,而对于引用类型也能很好地处理(在内部,List<T>
管理一个数组,每次空间不足时都会增加两倍的容量)。LinkedList<T>
曾经更有意义。人们经常引用其看似“O(1)”的特性,但这忽略了获取节点时出现页面错误的真实成本。List<T>
获得连续的内存区域并避免潜在的页面错误,则在现代处理器和主存储器缓存线方面会更好。List<T>
(并在构造函数中传递可能的上限以避免重新分配)。
如果你需要不断地将列表中的项目向前移动一个值,那么我唯一会使用 LinkedList<T>
,例如实现 最近最少使用 缓存算法时需要在前面添加内容并从末尾删除。
对于小项目,这确实不会有太大影响。分代垃圾收集器会随着时间的推移将散乱的堆项紧密地压缩在一起,因此链表不会变得太糟糕。
我会选择 List<T>
并运行它,除非你通过分析发现问题。
除非你处理的条目数量达到数十万或数百万,并且你已经分析了你的程序以确定存在主要问题,否则你可能不会注意到这两者之间的差异。
除此之外:
LinkedList<T>
提供了类型为LinkedListNode<T>
的单独节点,因此插入和删除是 O(1) 操作。
来自这里。
LinkedList<T>
。两种方式差别不大,但是LinkedList在添加元素时可能更快。ICollection<T>
而不是引用特定的具体类。List
,那么您可能会编写一堆使用l[0]
获取第一个项目的代码。另一方面,如果您使用LinkedList
,则可能会在代码中分散调用AddLast
。为了保留更改选择的权利,您需要避免无意中依赖您实际上不需要的功能。您需要使用两个容器都支持的接口。public static class Collections
{
public static ICollection<T> Make<T>()
{
return new List<T>();
}
}
那么每当你需要一个集合时,执行以下操作:
ICollection<int> c = Collections.Make<int>();
将容器的选择与程序的其余部分隔离开来。现在,当您进行分析并改变主意时,您只需编辑Make<T>
方法即可。