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

Summary ArrayList和ArrayDeque在many个以上的用例中比LinkedList个更好.如果你不确定，就从ArrayList开始.

TLDR，在ArrayList中，访问一个元素需要恒定的时间[O(1)]，添加一个元素需要O(n)个时间[最坏情况].在LinkedList中，添加元素需要O(n)个时间，访问也需要O(n)个时间，但LinkedList比ArrayList使用更多内存.

LinkedList和ArrayList是列表接口的两种不同实现.LinkedList通过一个双链接列表来实现它.ArrayList通过动态调整数组大小来实现它.

与标准链表和数组操作一样，不同的方法将有不同的算法运行时.

LinkedList<E>美元

• get(int index)是O(n)(平均n/4步)，但index = 0或index = list.size() - 1时是O(1)(在本例中，您也可以使用getFirst()和getLast()).One of the main benefits of LinkedList<E>
• add(int index, E element)是O(n)(平均n/4步)，但index = 0或index = list.size() - 1时是O(1)(在本例中，您也可以使用addFirst()和addLast()/add()).One of the main benefits of LinkedList<E>
• remove(int index)是O(n)(平均n/4步)，但index = 0或index = list.size() - 1时是O(1)(在本例中，您也可以使用removeFirst()和removeLast()).One of the main benefits of LinkedList<E>
• Iterator.remove()等于O(1).One of the main benefits of LinkedList<E>
• ListIterator.add(E element)等于O(1).One of the main benefits of LinkedList<E>

^{注意:许多操作平均需要n/4个步骤，最佳情况下需要constant个步骤(例如索引=0)，最坏情况下需要n/2个步骤(列表中间)}

ArrayList<E>美元

• get(int index)等于O(1).Main benefit of ArrayList<E>
• add(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个步骤，最佳情况下需要constant个步骤(列表末尾)，最坏情况下需要n个步骤(列表开头)}

LinkedList<E>允许恒定时间的插入或移除using iterators，但仅允许元素的顺序访问.换句话说，你可以向前或向后浏览列表，但是在列表中找到一个位置需要与列表大小成比例的时间.Javadoc说是"operations that index into the list will traverse the list from the beginning or the end, whichever is closer"，所以这些方法平均是O(n)(n/4步)，尽管index = 0步是O(1)步.

另一方面，ArrayList<E>允许快速随机读取访问，因此您可以在固定时间内获取任何元素.但是，除了结尾之外，任何地方的添加或删除都需要将后面的元素全部转移，要么形成一个开口，要么填补空白.此外，如果添加的元素多于基础数组的容量，则会分配一个新数组(大小的1.5倍)，并将旧数组复制到新数组，因此在最坏的情况下，添加到ArrayList是O(n)，但平均不变.

因此，根据您打算执行的操作，您应该相应地 Select 实现.迭代任何一种列表实际上都同样便宜.(从技术上讲，迭代超过ArrayList会更快，但是除非您正在做一些对性能非常敏感的事情，否则您不应该担心这一点--它们都是常量.)

当您重复使用现有迭代器来插入和删除元素时，使用LinkedList的主要好处就出现了.然后，通过仅在本地更改列表，可以在O(1)中完成这些操作.在数组列表中，数组的其余部分需要为moved(即复制).另一方面，在LinkedList中搜索意味着在最坏情况下遵循O(n)(n/2步)中的链接，而在ArrayList中，所需位置可以通过数学计算并在O(1)中访问.

使用LinkedList的另一个好处是在列表的开头添加或删除，因为这些操作是O(1)，而它们是O(n)代表ArrayList.请注意，对于从头部添加和移除，ArrayDeque可能是LinkedList的良好替代品，但它不是List.

此外，如果你有大的列表，记住内存使用也是不同的.LinkedList的每个元素都有更多的开销，因为指向下一个和上一个元素的指针也被存储.ArrayLists.不要把这项开销加在头上.然而，ArrayLists占用的内存与为容量分配的内存一样多，而不管是否实际添加了元素.

ArrayList的默认初始容量非常小(Java1.4-1.8中的10).但由于底层实现是一个数组，如果添加了大量元素，则必须调整数组的大小.要避免在知道要添加大量元素时调整大小的高成本，请使用更高的初始容量构建ArrayList.

如果使用data structures透视图来理解这两种 struct ，则LinkedList基本上是一种包含头部 node 的顺序数据 struct .该 node 是两个组件的包装器:类型为T的值[通过泛型接受]和对链接到它的 node 的另一个引用.因此，我们可以断言它是一个递归的数据 struct (一个 node 包含另一个 node ，而另一个 node 又有另一个 node ，以此类推……).如上所述，在LinkedList中添加元素需要线性时间.

ArrayList是一个可增长的array.它就像一个常规array.在引擎盖下，当添加一个元素时，ArrayList已经满了容量，它会创建另一个大小大于以前大小的array.然后将元素从上一个数组复制到新数组，并将要添加的元素也放置在指定的索引处.