何时在 Java 中使用 LinkedList 而不是 ArrayList？

扎弹

我一直是一个简单的人：

List names = new ArrayList();
0 r* g7 o0 `. S* @( [: {, f/ p9 H

我使用 interface 作为portability所以当我提出这样的问题时，我可以重写我的代码。
* u) y. r  V7 U: y- Z什么时候么时候？LinkedList用完，ArrayList反之亦然？
4 P% a) }: a" Q  \4 s  k                                                               
7 l& S1 ]& }5 n$ g, ~    解决方案:                                                               
2 ~2 I- q( ~. [9 H2 A6 {  h2 q( }' F                                                                在更多ArrayList的用例中，总结比.如果你不确定 - 只需从.ArrayDeque``LinkedList``ArrayList
TLDR，在 ArrayList 在 中访问一个元素需要时间[O(1)，需要 素需要 O(n) 时间[最坏情况]。LinkedList 需要 添加元素O(n) 时间，访问也需要  O(n) 时间，但 LinkedList 比 ArrayList 使用更多内存。
LinkedList并且ArrayList是 List 接口的两种不同实现。LinkedList用双向链表实现。ArrayList使用动态调整大小的数组来实现它。
与标准链表和数组操作一样，各种方法在运行时会有不同的算法。
为了 LinkedList
) j+ D' C- ]9 G$ [6 dget(int index)是O(n)（平均有n/4步），但O(1)    when index = 0or index = list.size() - 1(也可以在这种情况下使用getFirst()and getLast()）。主要好处之一    LinkedList
, Q& b" R2 ^! E) e/ \: hadd(int index,E element)是O(n)（平均有n/4步)，但是O(1)    when index = 0or index = list.size() - 1(也可以在这种情况下使用addFirst()and addLast()/ add()）。主要好处之一    LinkedList
8 g) Q( F" X' o) Y6 tremove(int index)是O(n)（平均有n/4步），但O(1)    when index = 0or index = list.size() - 1(也可以在这种情况下使用removeFirst()and removeLast()）。的主要好处之一    LinkedList
Iterator.remove()是O(1)。主要好处之一    LinkedList
$ Y) N8 n5 y* R% kListIterator.add(E element)是O(1)。主要好处之一    LinkedList注:平均需要很多操作:n/4步骤，在最佳情况下(如  index = 0）需要在最坏的情况下，恒定步数需要n/2步骤(列表中间)
2 A, _8 q" s3 h. A0 t为了 ArrayList
. E" R! d6 b  Sget(int index)是O(1)。主要好处    ArrayList
4 b% a2 f+ x8 x) j! O- m; Madd(E element)是O(1)摊销，但O(n)最坏的情况是必须调整数组的大小和复制
, w3 s# X6 i  O( badd(int index,E element)是O(n)（平均有n/2步）
remove(int index)是O(n)（平均有n/2步）
Iterator.remove()是O(n)（平均有n/2步）
2 }& l) r* f) {* t  L" @1 SListIterator.add(E element)是O(n)（平均有n/2步）注:平均需要很多操作:n/2步骤，最佳步数(列表末尾)恒定，最坏的情况(列表开头)需要n步
LinkedList`允许*使用迭代器*插入或删除恒定时间，但只能按顺序访问元素。换句话说，你可以向前或向后看列表，但在列表中找到位置所花费的时间与列表的大小成正比。Javadoc 说*索引到列表的操作将从头到尾遍历列表，以接近者为准*，所以这些方法平均是*O* *(n)*（*n/4*步骤)，尽管对.`index = 0ArrayList，另一方面，允许快速随机阅读访问，因此您可以在恒定的时间内捕获任何元素。但是，添加或删除任何地方，但最终需要转移背后的所有元素，要么打开开口，要么填补空白。此外，如果添加的元素大于底层数组的容量，则将分配一个新数组（大小 1.5 倍)，并将旧数组复制到新数组，因此添加到 an最坏的情况ArrayList是O(n)但平均情况保持不变。
因此，根据您计划执行的操作，您应该选择相应的实现。迭代任何 List 其实同样便宜。(迭代 anArrayList技术上更快，但除非你真的对性能敏感，否则你不应该担心这一点——它们都是常数。
LinkedList`当您重用现有的迭代器插入和删除元素时，使用 a 的主要好处就出现了。然后可以通过仅在本地更改列表在*O(1)完成这些操作。*在数组列表中，需要在数组列表中*移动*(即复制)。另一方面，在最坏的情况下，根据*O(n)*`LinkedList`中的链接（*n/2*步骤)寻找方法，可以通过数学计算在所需位置*O(1)*中访问。`ArrayListLinkedList添加或删除列表头部时，使用 a 的另一个好处是，因为这些操作是O(1)    ，对，它们是O(n)ArrayList。请注意，这ArrayDeque可能是LinkedList添加和删除头部是一个很好的替代方法，但它不是List.
另外，如果您有大型列表，请记住内存使用量也不同。a 的每一个元素LinkedList因为指向下一个和前一个元素的指针也存储在更多的费用中。ArrayLists没有这样的费用。ArrayLists无论元素是否实际添加，都会占用容量分配的内存。
an 默认初始容量ArrayList非常小（Java 1.4 - 1.8 是 10)。然而，由于底层实现是一个数组，如果添加了大量元素，则必须调整数组的大小。当您知道添加大量元素时，请避免高成本的大小调整ArrayList构建初始容量较高。
假从数据结构的角度理解这两种结构，LinkedList 基本上是包含头节点的顺序数据结构。Node 是两个组件的包装器:一个 T 类型值 [通过泛型接受] 和另一个链接Node 引用。因此，我们可以断言它是一个递归数据结构(一个节点包含另一个节点，另一个节点有另一个节点，等等......）。如上所述，在 LinkedList在 中添加元素需要线性时间。
7 f( C' Y$ r% oArrayList 是一个可生长的数组。它就像一个常规数组。在后台，添加元素并 ArrayList 满载时，创建另一个大于以前大小的数组。然后将元素从以前的数组复制到新的数组，并将要添加的元素放置在指定的索引中。