LinkedList和ArrayList的区别以及各自引用场景是什么？｜ Java Debug 笔记

本文正在参加「Java主题月 – Java Debug笔记活动」，详情查看<活动链接>

提问：LinkedList和ArrayList的区别以及各自引用场景是什么？

下面是我最常用的写法：

List<String> names = new ArrayList<>();
复制代码

我使用接口作为变量的类型，所以我可以方便的重构我的代码。
我们到底什么时候该用LinkedList，什么时候该用ArrayList呢？

最热门回答

摘要：ArrayList和ArrayDeque在许多用例上要比LinkedList表现优秀。如果你不确定用什么——就用ArrayList吧

这篇文章非常长，如果时间不够,看摘要就行。
ArrayList访问元素的时间复杂度为O(1)，添加元素的时间复杂度为O(n)[最坏情况下]。LinkedList添加元素的时间复杂度为O(n),访问元素的时间复杂度同样为O(n),但是LinkedList花费的内存要比ArrayList更多。

LinkedList和ArrayList是List接口的不同实现。LinkedList通过一个双向链表实现它。ArrayList通过一个动态数组实现。

与标准链表和数组操作一样，他们的许多方法都有不同的算法运用场景。

对于LinkedList<E>

• get(int index) 时间复杂度是O(n)，但是当index=0或index=list.size-1时，时间复杂度是O(1)，也可以直接用getFirst()和getLsat()获取值。这是LinkedList<E>的主要好处之一。
• add(int index, E element)的时间复杂度是O(n)，但是当index=0或index=list.size-1时，时间复杂度是O(1)，也可以直接用addFist()和addLsat()/add()添加值。这是LinkedList<E>的主要好处之一。
• remove(int index)的时间复杂度是O(n)，但是当index=0或index=list.size-1时，时间复杂度是O(1)，也可以直接用remove()和removeLsat()删除元素。这是LinkedList<E>的主要好处之一。
• Iterator.remove()的时间复杂度是O(1)
• ListIterator.add(E element),的时间复杂度是O(1)

对于ArrayList<E>

• get(int index)的时间复杂度是O(1)
• add(E element)的平摊时间复杂度是O(1)，但是在需要调整数组容量复制元素时，时间复杂度为最坏O(n)
• add(int index, E element)，时间复杂度是O(n)
• remove(int index)，时间复杂度是O(n)
• Iterator.remove()，时间复杂度是O(n)
• ListIterator.add(E element)，时间复杂度是O(n)

LinkedList<E>使用迭代器时允许进行常量时间的插入和移除元素，但是只能按照元素顺序一步步来。换句话说，你可以向前或向后浏览列表，但是找到一个节点的时间与列表的大小成比例。javadoc说索引遍历集合要么从集合开头开始，要么从集合结尾开始，取决于哪边离元素更接近。所以这些方法的平均时间复杂度为O(n),尽管index=0时的时间复杂度为O(1)

ArrayList<E>允许快速随机访问，所以你可以在常量时间内获取任何一个元素。但是，除了集合最后一个元素外，任何地方的添加或删除，都要将数组里的元素挪位置，要么是动态扩容数组，要么是把删除节点后的所有元素往前挪。此外，如果你新增元素的数量超过了底层数组容量，将会创建一个1.5倍容量的新数组。并且旧数组将会被复制到新数组中。向ArrayList<>中添加元素最坏情况下时间复杂度是O(n),但平均来说时间复杂度是常数。

所以根据你打算的操作，你需要相应的选择实现。在任何一种集合上迭代几乎都是同样方便。（用ArrayList迭代在技术上会更快，除非你在做一些真正性能敏感的事情，否则你不必担心用哪个实现类，他们的时间复杂度都是常量）

使用LinkedList最大的好处是，当你使用一个现有的迭代器插入或移除元素时，这些操作通过在本地改变列表可以在O(1)时间复杂度内完成。在数组列表中，数组的其余部分需要移动复制来完成。另一方面，在LinkedList中查询元素最坏情况下需要O(n)的时间复杂度，而在ArrayList中查找所需位置，可以用数学方法计算并在O(1)时间复杂度内访问。

另一个使用LinkedList的好处是，当你从，当你从列表的头或尾删除元素花费的时间复杂度为O(1)，相同操作用ArrayList时间复杂度时O(n)。ArrayDeque也许是LinkedList很好的一个替代方案，用来从头尾删除或插入元素，但它不是一个List。

此外，如果有一个数据量很大的列表，请记住，他们的内存使用也是不同的。LinkedList的每个元素都有更多的开销，因为指向下一个和上一个元素的指针也会被存储。而ArrayList并没有指针上的开销。但是不管实际上有没有添加元素，ArrayList占用的内存与为容量分配的内存一样多。

ArrayList底层数组默认容量非常小，从JAVA1.2-1.8容量为10。但由于底层实现是一个数组，因此如果添加了大量元素，则必须调整数组大小。如果集合中有大量元素，为了避免消耗大量资源去为数组扩容。你最好给数组初始化更大的容量。

如果从数据结构的角度来理解这两种结构，LinkedList基本上是宝航一个头节点的顺序数据结构。一个节点包含两个组件：一个类型为泛型T的值，和一个用来连接其它节点的指针。所以，我们可以断言它是一个递归数据结构（一个节点包含另一个节点，而另一个节点中又有另一个节点，以此类推……）。综上所述，在LinkedList中添加元素需要线性时间。

ArrayList是一个可增长的数组。他就像一个普通数组。当在索引i处添加元素，将创建另一个比以前数组容量大1的数组。然后将元素从旧数组拷贝到新数组中，并且将要被添加的元素，也会被放在指定的索引处。

文章翻译自Stack Overflow：stackoverflow.com/questions/3…