什么时候使用List和LinkedList更好?
当前回答
我同意上面提到的大部分观点。我也同意,在大多数情况下,List看起来是一个更明显的选择。
但是,我只是想补充一点,在很多情况下,LinkedList比List更有效。
假设你正在遍历元素,你想要执行大量的插入/删除;LinkedList在线性O(n)时间内完成,而List在二次O(n²)时间内完成。 假设你想一次又一次地访问更大的对象,LinkedList就变得非常有用。 Deque()和queue()更好地使用LinkedList实现。 当你处理很多更大的对象时,增加LinkedList的大小会更容易和更好。
希望有人会觉得这些评论有用。
其他回答
List和LinkedList之间的区别在于它们的底层实现。List是基于数组的集合(ArrayList)。LinkedList是基于节点指针的集合(LinkedListNode)。在API级别的使用上,它们几乎是相同的,因为它们都实现了相同的接口集,如ICollection、IEnumerable等。
关键的区别在于性能问题。例如,如果您正在实现具有大量“INSERT”操作的列表,LinkedList的性能优于list。因为LinkedList可以在O(1)时间内完成,但是List可能需要扩展底层数组的大小。要了解更多信息/细节,你可能想要阅读LinkedList和数组数据结构之间的算法差异。http://en.wikipedia.org/wiki/Linked_list和Array
希望这能有所帮助,
当您需要内置索引访问、排序(以及二进制搜索之后)和“ToArray()”方法时,您应该使用List。
我问了一个类似的关于LinkedList集合性能的问题,发现Steven Cleary的Deque c#实现是一个解决方案。与Queue集合不同,Deque允许前后移动项目。它类似于链表,但性能有所改进。
使用LinkedList的常见情况是这样的:
假设您想要从一个字符串列表中删除许多特定的字符串,这些字符串的大小很大,比如100,000。要删除的字符串可以在HashSet dic中查找,字符串列表中应该包含30,000到60,000个这样的需要删除的字符串。
那么用于存储100,000个字符串的列表的最佳类型是什么?答案是LinkedList。如果它们存储在数组列表中,则遍历它并删除匹配的字符串将占用 到数十亿次操作,而使用迭代器和remove()方法只需要大约100,000次操作。
LinkedList<String> strings = readStrings();
HashSet<String> dic = readDic();
Iterator<String> iterator = strings.iterator();
while (iterator.hasNext()){
String string = iterator.next();
if (dic.contains(string))
iterator.remove();
}
在大多数情况下,List<T>更有用。LinkedList<T>在列表中间添加/删除项时成本更低,而list <T>只能在列表末尾添加/删除项。
LinkedList<T>只有在访问顺序数据(向前或向后)时才最有效-随机访问相对昂贵,因为它每次都必须遍历链(因此它没有索引器)。但是,因为List<T>本质上只是一个数组(带有包装器),所以随机访问是可以的。
List<T>还提供了很多支持方法- Find, ToArray等;然而,这些也可以通过扩展方法用于。net 3.5/ c# 3.0的LinkedList<T> -所以这不是一个因素。
推荐文章
- 如何创建数组。包含不区分大小写的字符串数组?
- 检查字符串是否包含字符串列表中的元素
- 最好的方法在asp.net强制https为整个网站?
- 将字符串转换为System.IO.Stream
- 如何从枚举中选择一个随机值?
- 驻留在App_Code中的类不可访问
- 在链式LINQ扩展方法调用中等价于'let'关键字的代码
- dynamic (c# 4)和var之间的区别是什么?
- Visual Studio: ContextSwitchDeadlock
- 返回文件在ASP。Net Core Web API
- 自定义HttpClient请求头
- 如果我使用OWIN Startup.cs类并将所有配置移动到那里,我是否需要一个Global.asax.cs文件?
- VS2013外部构建错误"error MSB4019: The imported project <path> was not found"
- 从另一个列表id中排序一个列表
- 等待一个无效的异步方法