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

扎弹

我一直是一个简单的人：

List names = new ArrayList();
1 x& r4 c0 q9 k  d4 W6 t5 W

我使用 interface 作为portability所以当我提出这样的问题时，我可以重写我的代码。
什么时候么时候？LinkedList用完，ArrayList反之亦然？
                                                               
    解决方案:                                                               
$ a+ Y  S5 S$ {$ `) Q8 e                                                                在更多ArrayList的用例中，总结比.如果你不确定 - 只需从.ArrayDeque``LinkedList``ArrayList
TLDR，在 ArrayList 在 中访问一个元素需要时间[O(1)，需要 素需要 O(n) 时间[最坏情况]。LinkedList 需要 添加元素O(n) 时间，访问也需要  O(n) 时间，但 LinkedList 比 ArrayList 使用更多内存。
/ y4 T; e/ H% Q: ]LinkedList并且ArrayList是 List 接口的两种不同实现。LinkedList用双向链表实现。ArrayList使用动态调整大小的数组来实现它。
% |! Q# @: [0 }: Y* `. H* Z$ z与标准链表和数组操作一样，各种方法在运行时会有不同的算法。
为了 LinkedList
! g8 ]5 E$ v5 L) U! L& cget(int index)是O(n)（平均有n/4步），但O(1)    when index = 0or index = list.size() - 1(也可以在这种情况下使用getFirst()and getLast()）。主要好处之一    LinkedList
6 M' ]+ Q1 F8 j3 l( nadd(int index,E element)是O(n)（平均有n/4步)，但是O(1)    when index = 0or index = list.size() - 1(也可以在这种情况下使用addFirst()and addLast()/ add()）。主要好处之一    LinkedList
2 d! j8 K: L8 X6 c0 L/ M( N' t* Iremove(int index)是O(n)（平均有n/4步），但O(1)    when index = 0or index = list.size() - 1(也可以在这种情况下使用removeFirst()and removeLast()）。的主要好处之一    LinkedList
* Y% \8 b$ C; c' zIterator.remove()是O(1)。主要好处之一    LinkedList
; p% m% C" j1 b3 {9 T# I( a3 d# PListIterator.add(E element)是O(1)。主要好处之一    LinkedList注:平均需要很多操作:n/4步骤，在最佳情况下(如  index = 0）需要在最坏的情况下，恒定步数需要n/2步骤(列表中间)
0 M4 O+ h1 n2 q7 c为了 ArrayList
# U6 |7 J& ?- P: [) ^# _get(int index)是O(1)。主要好处    ArrayList
& w3 h& P$ p& v( \add(E element)是O(1)摊销，但O(n)最坏的情况是必须调整数组的大小和复制
add(int index,E element)是O(n)（平均有n/2步）
7 b( Q% G. E: l# |# K! [7 q2 `2 iremove(int index)是O(n)（平均有n/2步）
Iterator.remove()是O(n)（平均有n/2步）
ListIterator.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技术上更快，但除非你真的对性能敏感，否则你不应该担心这一点——它们都是常数。
) C& A" t; i$ w, N! G3 @& hLinkedList`当您重用现有的迭代器插入和删除元素时，使用 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构建初始容量较高。
# |' K8 X) p! B5 t! @假从数据结构的角度理解这两种结构，LinkedList 基本上是包含头节点的顺序数据结构。Node 是两个组件的包装器:一个 T 类型值 [通过泛型接受] 和另一个链接Node 引用。因此，我们可以断言它是一个递归数据结构(一个节点包含另一个节点，另一个节点有另一个节点，等等......）。如上所述，在 LinkedList在 中添加元素需要线性时间。
ArrayList 是一个可生长的数组。它就像一个常规数组。在后台，添加元素并 ArrayList 满载时，创建另一个大于以前大小的数组。然后将元素从以前的数组复制到新的数组，并将要添加的元素放置在指定的索引中。