Java中的LinkedList与ArrayList的区别

文
章
目
录

• 1.LinkedList与ArrayList的内部实现区别
• 2.性能上的区别
• 2.1. 添加元素
• 2.2. 移除元素
• 2.3. 迭代
• 2.4. 获取元素
• 3.结论

在Java中，ArrayList和LinkedList都是集合框架的成员。它们实现java.util.List接口，提供了在有序集合中存储和获取对象的能力。它们都是非同步类，但在许多方面有所不同，我们需要详细了解这两个类，以明智地决定何时使用哪个类。

1.LinkedList与ArrayList的内部实现区别

LinkedList是Java中的双向链表实现。LinkedList中的每个对象都被包装在一个Node实例中。

transient Node<E> first;
transient Node<E> last;
private static class Node<E> {
  E item;
  Node<E> next;
  Node<E> prev;
}

ArrayList被实现为动态调整大小的数组。这将导致性能上的进一步差异。

transient Object[] elementData;

请注意，这两个列表都允许重复元素并保持元素的插入顺序。在LinkedList中，元素具有对下一个和上一个元素的引用。

2.性能上的区别

2.1. 添加元素

在ArrayList中添加一个元素是O(1)操作，如果不需要调整支持数组的大小。如果数组需要调整大小，那么它将变为O(log(n))。

在LinkedList中添加一个元素是O(1)操作，因为它不需要任何调整大小。

2.2. 移除元素

当从ArrayList中移除一个元素（在支持数组中），它会移动被移除索引位置之后的所有元素。这在最坏情况下，当我们移除第一个元素时，接近O(n)的性能。在最好的情况下，当移除最后一个元素时，性能为O(1)。

LinkedList的remove()操作性能为O(1)，因为它只需要重置前一个和后一个节点的指针。不需要复制或移动。

2.3. 迭代

当列表包含’n’个项目时，迭代对于LinkedList和ArrayList都是O(n)操作。

2.4. 获取元素

ArrayList提供get(int index)方法，可以直接找到给定索引位置的元素。其时间复杂度为O(1)。

LinkedList也提供get()方法，但它首先需要遍历所有节点以达到正确的节点。这使性能变量化。在最佳情况下，它是O(1)，在最坏情况下，它是O(n)。

3.结论

除非我们处理非常大量的数据，否则这两个类将为我们提供相同级别的性能。它们都是有序列表，而且都是非同步的。

LinkedList还实现了Deque接口，因此它通过peek()和poll()等方法提供了类似队列的FIFO功能。正如在性能比较中所看到的，ArrayList更适合存储和访问数据，而LinkedList更适合操作数据。

这就是关于Java中ArrayList与LinkedList的区别的全部内容。