LinkedList和ArrayList有什么区别,什么时候使用哪一个？

Question

LinkedList和之间有什么区别ArrayList？我怎么知道何时使用哪一个？

Answer 1

区别在于用于存储对象的内部数据结构.

一个ArrayList将使用一个系统阵列(像Object[])并在需要时调整其大小.另一方面,a LinkedList将使用包含数据的对象和指向列表中下一个和上一个对象的指针.

由于内部表示的这种差异,不同的操作将具有不同的算法复杂度.

Answer 2

不要使用任何一种.使用System.Collections.Generic.List<T>.

这真的是我的建议.可能与您的应用程序无关,但这里有更多的颜色,以防您在这里做一些需要精心调整的选择.

ArrayList并且LinkedList是用于a的存储机制的不同实现List.ArrayList如果您的集合超出当前存储大小,则使用必须调整大小的数组.LinkedList另一方面,使用来自CS 201的链表数据结构.LinkedList对于一些头部或尾部插入繁重的工作负载ArrayList更好,但对于随机访问工作负载更好.

Answer 3

ArrayList有一个很好的替代品List<T>.

通常,List<T>是数组的包装器 - 它允许索引和访问O(1)中的项目,但是,每次超出容量时,必须支付O(n).

LinkedList<T>不允许您使用索引访问项目,但您可以计算该插入总是花费O(1).此外,您可以将项目插入列表的开头以及O(1)中的现有项目之间.

我认为在大多数情况下List<T>是默认选择.许多常见场景不需要特殊顺序并且没有严格的复杂性约束,因此List<T>由于其使用简单而是优选的.

Answer 4

ArrayList和List<T>、LinkedList<T>、 以及其他类似的泛型之间的主要区别在于，它ArrayList保存Objects，而其他泛型保存您指定的类型（即List<Point>仅保存 Points）。

因此，您需要将从中取出的任何对象转换为其ArrayList实际类型。如果类名很长，这可能会占用大量屏幕空间。

List<T>一般来说，除非您确实需要一个包含多种不同类型对象的列表，否则使用其他类型的泛型要好得多。