章
目
录
在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的区别的全部内容。