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

提问：何时在Java中通过ArrayList使用LinkedList？

我一直是一个简单使用的人：

List names = new ArrayList<>();

我将接口用作可移植性的类型名称，这样，当我问诸如此类的问题时，便可以重新编写代码。

什么时候应该LinkedList使用过ArrayList，反之亦然？

高分回答：

TLDR在ArrayList中访问元素需要固定的时间[O（1）]，添加元素需要O（n）的时间[最坏的情况]。在LinkedList中，添加元素需要O（n）时间，而访问也需要O（n）时间，但是LinkedList使用的内存比ArrayList多。

LinkedList并且ArrayList是List接口的两种不同的实现。LinkedList用双向链表实现它。ArrayList用动态调整大小的数组实现它。

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

LinkedList

• get(int index)是O（n）（平均n / 4步），但在或时为O（1）（在这种情况下，您也可以使用和）。的主要好处之一index = 0index = list.size() - 1getFirst()getLast() LinkedList

• add(int index, E element)是O（n）（平均为n / 4步），但是当或时为O（1）（在这种情况下，您也可以使用和/ ）。的主要好处之一index = 0index = list.size() - 1addFirst()addLast()add()

  LinkedList

• remove(int index)是O（n）（平均n / 4步），但在或时为O（1）（在这种情况下，您也可以使用和）。的主要好处之一index = 0index = list.size() - 1removeFirst()removeLast() LinkedList

• Iterator.remove()是O（1）。的主要好处之一 LinkedList ListIterator.add(E element)是O（1）。的主要好处之一 LinkedList

注意：许多操作平均需要n / 4步，在最佳情况下（例如，索引= 0）需要恒定的步数，在最坏情况下（列表的中间）需要n / 2步

ArrayList

• get(int index)是O（1）。主要优点 ArrayList
• 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步，在最佳情况下（列表结束）需要恒定的步数，在最坏情况下（列表开始）需要n步

LinkedList允许使用迭代器进行固定时间的插入或删除，但只能顺序访问元素。换句话说，您可以向前或向后浏览列表，但是在列表中查找位置所花费的时间与列表的大小成正比。 Javadoc说：“索引到列表中的操作将从开头或结尾遍历列表，以较近者为准”，因此，这些方法的平均值为O（n）（n / 4步），尽管O（1）为index = 0。

ArrayList另一方面，允许快速随机读取访问，因此您可以在固定时间内抓取任何元素。但是，从末端开始的任何地方添加或删除，都需要将后面的所有元素移开，以形成开口或填补空白。另外，如果添加的元素多于基础数组的容量，则会分配一个新数组（大小的1.5倍），并将旧数组复制到新数组中，因此在最差的情况下将a添加ArrayList为O（n）情况，但平均保持不变。

因此，根据您打算执行的操作，您应该相应地选择实现。在任何一种List上进行迭代实际上都是很便宜的。 （从ArrayList技术上讲，迭代速度更快，但是除非您执行的操作确实对性能敏感，否则您不必担心这一点-它们都是常量。）

LinkedList当您重复使用现有迭代器来插入和删除元素时，使用generic的主要好处。然后可以通过仅在本地更改列表在O（1）中完成这些操作。在阵列列表中，阵列的其余部分需要移动（即复制）。另一方面，在最坏的情况下LinkedList以O（n）（n / 2步）的链接寻找均值，而在ArrayList所需位置可以数学计算并在O（1）中访问。

使用的另一个好处LinkedList出现当您从列表的头部添加或删除，因为这些操作是O（1） ，而他们是为O（n）进行ArrayList。请注意，这ArrayDeque可能是LinkedList添加和删​​除头部的不错选择，但不是List。

另外，如果列表很大，请记住，内存使用情况也有所不同。a的每个元素LinkedList都有更多的开销，因为还存储了指向下一个和上一个元素的指针。ArrayLists没有这个开销。但是，ArrayLists无论是否实际添加了元素，占用的内存都应为该容量分配的内存。

的默认初始容量ArrayList很小（Java 1.4-1.8中为10）。但是由于底层实现是一个数组，因此如果添加很多元素，则必须调整数组的大小。为了避免在确定要添加很多元素时调整大小的高成本，请ArrayList以更高的初始容量构造。

如果使用数据结构透视图来理解这两种结构，则LinkedList基本上是一个顺序数据结构，其中包含头Node。Node是两个组件的包装：一个T类型的值（通过泛型接受）和对链接到它的Node的另一个引用。因此，我们可以断言这是一个递归数据结构（一个节点包含另一个节点，而另一个节点具有另一个节点，依此类推...）。如上所述，元素的添加在LinkedList中花费线性时间。

ArrayList是可增长的数组。它就像一个常规数组。在幕后，将一个元素添加到索引i时，它将创建另一个数组，该数组的大小比先前的大小大1（因此，通常，当将n个元素添加到ArrayList时，一个新的大小为先前大小的数组加n被创建）。然后将元素从先前的数组复制到新数组，并将要添加的元素也放置在指定的索引处。

文章翻译自 am2dgbqfb6mk75jcyanzabc67y-ac4c6men2g7xr2a-stackoverflow-com.translate.goog/questions/3…

作者建议：生产中注意ArrayList的容量，做一个整体的预估

真心感谢帅逼靓女们能看到这里，如果这个文章写得还不错，觉得有点东西的话

求点赞???? 求关注❤️ 求分享???? 对8块腹肌的我来说真的 非常有用！！！

如果本篇博客有任何错误，请批评指教，不胜感激 ！❤️❤️❤️❤️