在Java Collections框架中，有两个通用的List实现— ArrayList和LinkedList。在本文中，我们将看到ArrayList和LinkedList在Java中的区别，以更好地理解这两种实现。了解ArrayList和LinkedList之间的区别还将确定哪种实现在哪种情况下更好。

Java中的ArrayList与LinkedList

1如何在内部实施
ArrayList内部实现使用数组存储其元素。如果需要，可以动态增加数组的大小，这就是为什么ArrayList被称为可调整大小的数组实现的原因。
LinkedList在内部实现为双链表，其中元素存储为类型节点的对象。在除元素之外的节点对象中，还存储了前一个节点和下一个节点的引用。

2初始容量
ArrayList具有构造函数ArrayList(int initialCapacity)，可以构造指定容量的ArrayList。即使未指定初始容量，也将使用默认容量10创建ArrayList。
Java中的LinkedList没有任何初始容量，添加元素时会创建Node类型的对象。

3添加元素
即使未指定内部容量，Java中的ArrayList也会默认创建大小为10的数组。由于将数组创建为连续的内存块，因此在ArrayList中添加元素就像将元素放入下一个索引一样简单，但是涉及一些复杂性。
如果array已满，则在ArrayList中插入下一个元素将需要调整数组的大小并将ArrayList的所有现有元素移动到新数组。
如果将元素频繁添加到ArrayList的开头，那么还会增加移动数组中所有元素以放置新元素的开销。使用add(int index，E element)方法在指定位置添加元素时，添加元素的开销也相同。
在将元素添加到ArrayList时，通过所有这些可能性，ArrayList中的add操作以摊销的恒定时间运行，即，添加n个元素需要O(n)时间。

LinkedList插入为O(1)，因为添加元素仅需要调整上一个和下一个节点的引用。

但这里要注意的一件事是，与LinkedList实现相比，ArrayList中的常量因子较低。

4拆卸元件
从ArrayList中删除元素需要花费更少的时间到达要删除的元素(只需访问数组索引)，但是需要将所有元素移到必须删除的元素之后，以向后移动以填充已删除元素剩余的空间。因此，删除ArrayList的最后一个元素是O(1)，其中第一个元素是O(n)。

在LinkedList的情况下，性能也为O(n)，因为到达必须删除的元素是线性操作。同样，删除第一个元素的remove()和removeFirst()方法需要O(1)时间。使用removeLast()方法删除最后一个元素也将是O(1)，因为也会存储对最后一个节点的引用。

5访问元素
在ArrayList中，使用get(int index)方法检索元素是O(1)，因为它只需要访问该数组索引。
在LinkedList的get(int index)方法为O(n)的情况下，因为它需要线性遍历才能到达该索引。

6迭代时删除元素
在ArrayList中，在遍历List时删除元素仍然具有转移元素的开销。
在LinkedList中，在迭代列表时删除元素为O(1)，因为迭代器已经位于必须删除的元素上。

7整体表现
根据官方JavaDocs，与LinkedList相比，ArrayList应该是首选。
"如果我们想使用LinkedList，请在做出选择之前同时使用LinkedList和ArrayList来评估应用程序的性能； ArrayList通常更快。"