Java▲还不懂Java集合框架？看这一篇就够了( 二 ) 飞利浦·斯塔克

查下集合中有没有某个特定的元素：

boolean contains(Object o);

查集合 A 是否包含了集合 B：

boolean containsAll(Collection<?> c);

还有一些对集合整体的操作：

判断集合是否为空：

boolean isEmpty();

集合的大小：

int size();

把集合转成数组：

Object[
toArray();

以上就是 Collection 中常用的 API 了。
在接口里都定义好了，子类不要也得要。
当然子类也会做一些自己的实现，这样就有了不同的数据结构。
那我们一个个来看。
List
List 最大的特点就是：有序，可重复。
看官网说的：

An ordered collection (also known as a sequence).

Unlike sets lists typically allow duplicate elements.

这一下把 Set 的特点也说出来了，和 List 完全相反， Set 是无序，不重复的。
List 的实现方式有 LinkedList 和 ArrayList 两种，那面试时最常问的就是这两个数据结构如何选择。
对于这类选择问题：一是考虑数据结构是否能完成需要的功能；如果都能完成，二是考虑哪种更高效。
（万事都是如此啊。
那具体来看这两个 classes 的 API 和它们的时间复杂度：
稍微解释几个：
add(E e) 是在尾巴上加元素，虽然 ArrayList 可能会有扩容的情况出现，但是均摊复杂度（amortized time complexity）还是 O(1) 的。
add(int index E e)是在特定的位置上加元素， LinkedList 需要先找到这个位置，再加上这个元素，虽然单纯的「加」这个动作是 O(1) 的，但是要找到这个位置还是 O(n) 的。（这个有的人就认为是 O(1) ，和面试官解释清楚就行了，拒绝扛精。
remove(int index)是 remove 这个 index 上的元素，所以

ArrayList 找到这个元素的过程是 O(1) ，但是 remove 之后，后续元素都要往前移动一位，所以均摊复杂度是 O(n)；
LinkedList 也是要先找到这个 index ，这个过程是 O(n) 的，所以整体也是 O(n) 。

remove(E e)是 remove 见到的第一个这个元素，那么

ArrayList 要先找到这个元素，这个过程是 O(n) ，然后移除后还要往前移一位，这个更是 O(n) ，总的还是 O(n)；
LinkedList 也是要先找，这个过程是 O(n) ，然后移走，这个过程是 O(1) ，总的是 O(n).

那造成时间复杂度的区别的原因是什么呢？
答：

因为 ArrayList 是用数组来实现的。
而数组和链表的最大区别就是数组是可以随机访问的（random access）。

这个特点造成了在数组里可以通过下标用 O(1) 的时间拿到任何位置的数，而链表则做不到，只能从头开始逐个遍历。
也就是说在「改查」这两个功能上，因为数组能够随机访问，所以 ArrayList 的效率高。
那「增删」呢？
如果不考虑找到这个元素的时间，
数组因为物理上的连续性，当要增删元素时，在尾部还好，但是其他地方就会导致后续元素都要移动，所以效率较低；而链表则可以轻松的断开和下一个元素的连接，直接插入新元素或者移除旧元素。