什么时候使用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> -所以这不是一个因素。