Java 10 | 数据结构 - LinkedList 还是 ArrayList

Java 提供了 ArrayList, ArrayDeque 和 LinkedList 几个API.

队列 queue, 通俗的含义, 就是不能插队, 只能在末尾插入.

双端队列 Double Ended Queue (Deque) 是具有动态大小的序列容器，可以在两端（前端或后端）扩展或收缩 –http://www.cplusplus.com/reference/deque/deque/

CS61b的project 1a需要实现两种双端队列（array based 和 linkedklist based）.

不同的API, 在考虑什么时候应该用哪个时, 我们需要考虑它们的性能差异:

• 搜索/定位：与LinkedList相比，ArrayList搜索更快。 ArrayList的get(int index)性能是O(1)的，而LinkedList的性能是O(n)。因为ArrayList基于array数据结构，可以直接用 array index 定位元素。
• 删除/插入：LinkedList 操作性能是O(1)，而ArrayList的性能从O(n)（删除/插入第一个元素）到O(n)（最后一个元素）都有可能。因为LinkedList的每个元素都包含两个指向其相邻前后元素的指针（地址），因此仅需要改变，被删节点的prev和next指针位置。而在ArrayList中，需要移动剩余元素，来重新填充array空间。
• 内存开销：LinkedList的每个元素都有更多的内存开销(额外的指针), 而ArrayLists没有这个开销。但是，ArrayLists需要占用初始容量。一般ArrayList的默认初始容量非常小（Java 1.4 - 1.8使用10）。但是，往ArrayLists添加元素时， 它可能会适当地增大容量，所以如果添加了很多元素，则必须不断调整数组的大小，那样也可能会导致元素频繁挪动位置。

综上所述：

1. 如果在应用中需要频繁插入和删除，那么选择LinkedList。
2. 假如一开始，就知道后面要添加大量元素，那就使用较高的初始容量来构造ArrayList。
3. 大部分用例中, 相比LinkedList, 人们更偏爱ArrayList以及ArrayDeque。如果你不确定应该选哪个, 那么就直接考虑ArrayList吧(参考 https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist).