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

扎弹

我一直是一个简单的人：

List names = new ArrayList();

我使用 interface 作为portability所以当我提出这样的问题时，我可以重写我的代码。
5 E. {" R4 |0 k( Z3 Q9 |& j什么时候么时候？LinkedList用完，ArrayList反之亦然？
5 {: m3 ^# U4 I( S7 i* O                                                               
  `0 `& U! J& Z8 B    解决方案:                                                               
                                                                在更多ArrayList的用例中，总结比.如果你不确定 - 只需从.ArrayDeque``LinkedList``ArrayList
TLDR，在 ArrayList 在 中访问一个元素需要时间[O(1)，需要 素需要 O(n) 时间[最坏情况]。LinkedList 需要 添加元素O(n) 时间，访问也需要  O(n) 时间，但 LinkedList 比 ArrayList 使用更多内存。
" z! X4 X$ A5 X: u" O9 H; T$ M, HLinkedList并且ArrayList是 List 接口的两种不同实现。LinkedList用双向链表实现。ArrayList使用动态调整大小的数组来实现它。
与标准链表和数组操作一样，各种方法在运行时会有不同的算法。
! g8 v" i+ |  e) a6 Z7 ?/ G为了 LinkedList
get(int index)是O(n)（平均有n/4步），但O(1)    when index = 0or index = list.size() - 1(也可以在这种情况下使用getFirst()and getLast()）。主要好处之一    LinkedList
add(int index,E element)是O(n)（平均有n/4步)，但是O(1)    when index = 0or index = list.size() - 1(也可以在这种情况下使用addFirst()and addLast()/ add()）。主要好处之一    LinkedList
remove(int index)是O(n)（平均有n/4步），但O(1)    when index = 0or index = list.size() - 1(也可以在这种情况下使用removeFirst()and removeLast()）。的主要好处之一    LinkedList
" |# M5 v# W( x+ p1 q; CIterator.remove()是O(1)。主要好处之一    LinkedList
ListIterator.add(E element)是O(1)。主要好处之一    LinkedList注:平均需要很多操作:n/4步骤，在最佳情况下(如  index = 0）需要在最坏的情况下，恒定步数需要n/2步骤(列表中间)
4 p: {& z3 b: X) u/ F% M# p; x8 ^1 v为了 ArrayList
get(int index)是O(1)。主要好处    ArrayList
9 \9 m( Q5 I! k3 k$ W6 ]7 Xadd(E element)是O(1)摊销，但O(n)最坏的情况是必须调整数组的大小和复制
add(int index,E element)是O(n)（平均有n/2步）
remove(int index)是O(n)（平均有n/2步）
Iterator.remove()是O(n)（平均有n/2步）
ListIterator.add(E element)是O(n)（平均有n/2步）注:平均需要很多操作:n/2步骤，最佳步数(列表末尾)恒定，最坏的情况(列表开头)需要n步
( y8 ^+ m  e9 y0 K9 WLinkedList`允许*使用迭代器*插入或删除恒定时间，但只能按顺序访问元素。换句话说，你可以向前或向后看列表，但在列表中找到位置所花费的时间与列表的大小成正比。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.
5 w3 C% D* S3 m2 s/ }. w另外，如果您有大型列表，请记住内存使用量也不同。a 的每一个元素LinkedList因为指向下一个和前一个元素的指针也存储在更多的费用中。ArrayLists没有这样的费用。ArrayLists无论元素是否实际添加，都会占用容量分配的内存。
an 默认初始容量ArrayList非常小（Java 1.4 - 1.8 是 10)。然而，由于底层实现是一个数组，如果添加了大量元素，则必须调整数组的大小。当您知道添加大量元素时，请避免高成本的大小调整ArrayList构建初始容量较高。
+ z- v& F2 w: {) }  s假从数据结构的角度理解这两种结构，LinkedList 基本上是包含头节点的顺序数据结构。Node 是两个组件的包装器:一个 T 类型值 [通过泛型接受] 和另一个链接Node 引用。因此，我们可以断言它是一个递归数据结构(一个节点包含另一个节点，另一个节点有另一个节点，等等......）。如上所述，在 LinkedList在 中添加元素需要线性时间。
- `# S8 X/ y( O+ `' I! H8 ~5 ~) hArrayList 是一个可生长的数组。它就像一个常规数组。在后台，添加元素并 ArrayList 满载时，创建另一个大于以前大小的数组。然后将元素从以前的数组复制到新的数组，并将要添加的元素放置在指定的索引中。