大多数Java初学者在使用动态数组时，会不假思索的选择ArrayList。但实际上，除了ArrayList，还有LinkedList可供选用。
那么，在使用Java的动态数组时，怎样在ArrayList与LinkedList之间做出选择呢？
一言以蔽之，在大多数使用场景中，ArrayList与ArrayDeque要优于LinkedList。对于初学者来说，在拿不准用哪个时，不妨使用ArrayList。
LinkedList与ArrayList是List接口的两种不同的实现。LinkedList使用双向链表实现。ArrayList则使用动态可变长数组实现。
对于标准的链表和数组运算，不同的方法会有不同的算法运行时间。
对于LinkedList<E>：
- get(int index) O(n)
- add(E element) O(1)
- add(int index, E element) O(n)
- remove(int index) O(n)
- Iterator.remove() O(1) <--- LinkedList<E>的主要优势
- ListIterator.add(E element) O(1) <--- LinkedList<E>的主要优势
对于ArrayList<E>：
- get(int index) O(1) <--- ArrayList<E>的主要优势
- add(E element) O(1) （均摊）, 但最坏情况是 O(n) ，由于数组需要调整大小和复制
- add(int index, E element) O(n - index) 均摊, 但最坏情况 O(n) (理由同上)
- remove(int index) O(n - index) (i.e. removing last is O(1))
- Iterator.remove() O(n - index)
- ListIterator.add(E element) O(n - index)
LinkedList<E>在使用迭代器时支持常数时间的插入和移除操作，但是只允许顺序访问其中的元素。换言之，你可以向前或者向后遍历列表，但是访问列表中特定的位置花费的时间与列表的长度成比例。
ArrayList<E>，在另一方面，支持快速的随机读取访问，因此你可以在常数时间内抓取任何元素。但是添加或者移除末尾元素以外的任何元素都需要对其之后的元素进行评议操作，插入一个新元素的位置或者填补被移除元素的空缺。此外，如果你添加的元素多余底层数组的容量，一个新的数组（1.5倍长度）会被分配，然后旧数组中的元素会被拷贝至新的数组中，因此向ArrayList中添加元素在最坏情况下复杂度为O（n），但平均情况下还是常数时间。
因此取决于你想要执行的操作，然后据此选择实现。遍历任意一种列表的开销实际上都很低。（遍历ArrayList从技术角度来说更快，但除非你在做一些对性能异常敏感的东西，你不需要对此表示担心——它们都是常数时间的。）
当你重用既有的迭代器插入或者移除元素时，使用LinkedList的好处会变得比较明显。由于只是局部的更改列表，这些操作会在O(1)时间内完成。在ArrayList中，数组剩余的部分也需要被移动（i.e. 拷贝）。另一方面，在LinkedList中寻找元素意味着用O(n)的时间遍历链表，而在ArrayList中，目标位置可以通过数学计算，并在O（1）的时间内访问。
此外，如果列表中的元素很多时，请记住它们的内存开销是不一样的。LinkedList中的每个元素都需要占用额外的开销，由于需要保存next和prev元素的指针。而ArrayList不需要保存这些信息。不过，ArrayList占用的内存取决于它的容量，无论其中实际包含多少个元素。
ArrayList的缺省初始容量很小（Java 1.4 - 1.7为10）。但由于其底层用数组实现，如果你添加很多元素，数组必须被调整大小（resize）。为了避免调整大小带来的高额开销，当你知道你会添加许多元素时，在构建ArrayList时可以使用更高的初始容量。
同样实现List接口的Vector与ArrayList基本相同，但是价值不大。唯一的区别是Vector是同步的，因而是线程安全的。由此原因，它比ArrayList稍微慢一些。目前为止据我了解，大多数Java程序员不会去使用Vector，而只用ArrayList，因为如果他们需要线程安全时可以使用显示的同步方法（synchronize）
原文链接：http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist
本文链接：http://bookshadow.com/weblog/2014/11/23/java-linkedlist-vs-arraylist/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
