526互联

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

发布时间 2023-10-26 20:09:24作者: 小满独家

内容来自 DOC https://q.houxu6.top/?s=在Java中何时使用LinkedList而不是ArrayList？

我总是这样使用：

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

我使用接口作为可移植性的类型名称，以便当我提出这样的问题时，我可以重新调整我的代码。

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

总结：在许多用例中，与LinkedList相比，ArrayList和ArrayDeque更喜欢使用ArrayList。如果您不确定，请从ArrayList开始。

TLDR，在ArrayList中访问元素需要常数时间[O(1)]，添加元素需要O(n)时间[最坏情况]。在LinkedList中插入元素需要O(n)时间，访问也需要O(n)时间，但LinkedList使用的内存比ArrayList多。

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

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

对于LinkedList<E>：

  • get(int index)是O(n)（平均n/4步），但当index = 0或index = list.size() - 1时为O(1)（在这种情况下，您还可以使用getFirst()和getLast()）。LinkedList<E>的主要优点是其中之一。
  • add(int index, E element)是O(n)（平均n/4步），但当index = 0或index = list.size() - 1时为O(1)（在这种情况下，您还可以使用addFirst()和addLast()/add()）。LinkedList<E>的主要优点是其中之一。
  • remove(int index)是O(n)（平均n/4步），但当index = 0或index = list.size() - 1时为O(1)（在这种情况下，您还可以使用removeFirst()和removeLast()）。LinkedList<E>的主要优点是其中之一。
  • Iterator.remove()是O(1)。LinkedList<E>的主要优点是其中之一。
  • ListIterator.add(E element)是O(1)。LinkedList<E>的主要优点是其中之一。

注意：许多操作需要在平均情况下n/4步，在最好情况下（例如索引=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步），但在索引=0时为O(1)。

另一方面，ArrayList允许快速随机读取访问，因此您可以在常数时间内获取任何元素。但是，除末尾外，从任何地方添加或删除都需要移动所有后面的元素，要么打开空间，要么填补缺口。此外，如果您添加的元素数量超过底层数组的容量，将分配一个新的数组（1.5倍的大小），并将旧数组复制到新数组中，因此在最坏情况下向ArrayList添加是O(n)，但平均值下是常数。

因此，根据您打算执行的操作，应相应地选择实现。遍历任何一种列表实际上成本差不多。 （在技术上，遍历ArrayList更快，但除非您非常关注性能，否则不必担心这一点-它们都是常数。）
使用LinkedList的主要好处在于，当您重用现有的迭代器来插入和删除元素时。这些操作可以通过仅局部更改列表在O(1)时间内完成。在数组列表中，数组的剩余部分需要移动（即复制）。另一方面，在LinkedList中查找意味着按照O(n)（n/2步）跟踪链接，而在ArrayList中，所需位置可以通过数学计算并在O(1)时间内访问。

当您从列表的开头添加或删除元素时，使用LinkedList的另一个好处是，因为这些操作是O(1)，而对于ArrayList来说是O(n)。请注意，ArrayDeque可能是LinkedList的一个很好的替代选择，用于从开头添加和删除元素，但它不是List。

此外，如果您有大型列表，请记住，内存使用也有所不同。由于还存储指向下一个和上一个元素的指针，因此LinkedList的每个元素都有更多的开销。ArrayLists没有这种开销。然而，ArrayLists占用的内存与分配的容量相同，无论元素是否实际已添加。

ArrayList的默认初始容量相当小（从Java 1.4到1.8的10个单位）。但由于底层实现是数组，因此如果要添加大量元素，则必须调整数组大小。为了避免在知道要添加大量元素时调整大小的高成本，请使用较高的初始容量构造ArrayList。

如果从数据结构的角度来理解这两种结构，那么LinkedList基本上是一个顺序数据结构，它包含一个头节点。节点是包装两个组件的包装器：一个通过泛型接受的类型T的值，以及另一个指向与其链接的节点的引用。因此，我们可以断言它是一种递归数据结构（一个节点包含另一个节点，该节点又有一个节点，依此类推...）。如上所述，LinkedList中的元素添加需要线性时间。

ArrayList是一种可增长的数组。它就像一个常规数组。在底层，当元素被添加并且ArrayList已满时，它将创建一个比先前大得多的大小的新数组。然后，元素从先前的数组复制到新数组中，并且要添加的元素也放置在指定的索引处。