什么时候使用List和LinkedList更好?


当前回答

链表相对于数组的主要优点是,链接为我们提供了有效地重新排列项的能力。 塞奇威克,第91页

其他回答

当您需要内置索引访问、排序(以及二进制搜索之后)和“ToArray()”方法时,您应该使用List。

链表提供了快速插入或删除列表成员的功能。链表中的每个成员都包含指向链表中下一个成员的指针,因此要在位置i插入一个成员:

更新成员i-1中的指针,使其指向新成员 将新成员中的指针设置为指向成员I

链表的缺点是不能进行随机访问。访问成员需要遍历列表,直到找到所需的成员。

我同意上面提到的大部分观点。我也同意,在大多数情况下,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

希望这能有所帮助,

链表相对于数组的主要优点是,链接为我们提供了有效地重新排列项的能力。 塞奇威克,第91页