java - 何时在Java中通过ArrayList使用LinkedList？

Question

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

List<String> names = new ArrayList<>();

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

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

Answer 1

总结ArrayList和ArrayDeque在比LinkedList更多的用例中更可取。如果不确定，请从ArrayList开始。



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

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

对于LinkedList<E>


get(int index)是O（n）（平均n / 4步）
add(E element)是O（1）
add(int index, E element)是O（n）（平均n / 4步），
但是当index = 0 <---- LinkedList<E>主要好处时为O（1）
remove(int index)是O（n）（平均n / 4步）
Iterator.remove()是O（1）。 <--- LinkedList<E>的主要优点
ListIterator.add(E element)是O（1）这是LinkedList<E>的主要优点之一


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

对于ArrayList<E>


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

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

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

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

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

当您从列表的开头添加或删除列表时，使用ArrayList的另一个好处是，由于这些操作为O（1），而对于LinkedList为O（n）。请注意，ArrayList可能是ArrayDeque进行头部添加和从头部移除的一个很好的选择，但它不是LinkedList。

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

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