原文来自《Offer来了：Java面试核心知识点精讲》

Java的集合类被定义在Java.util包中，主要有4种集合，分别为List、Queue、Set和Map，每种集合的具体分类如图2-1所示。

2.1.1 List：可重复

List是非常常用的数据类型，是有序的Collection，一共有三个实现类，分别是ArrayList、Vector和LinkedList。

1．ArrayList：基于数组实现，增删慢，查询快，线程不安全

ArrayList是使用最广泛的List实现类，其内部数据结构基于数组实现，提供了对List的增加（add）、删除（remove）和访问（get）功能。

ArrayList的缺点是对元素必须连续存储，当需要在ArrayList的中间位置插入或者删除元素时，需要将待插入或者删除的节点后的所有元素进行移动，其修改代价较高，因此，ArrayList不适合随机插入和删除的操作，更适合随机查找和遍历的操作。

ArrayList不需要在定义时指定数组的长度，在数组长度不能满足存储要求时，ArrayList会创建一个新的更大的数组并将数组中已有的数据复制到新的数组中。

2．Vector：基于数组实现，增删慢，查询快，线程安全

Vector的数据结构和ArrayList一样，都是基于数组实现的，不同的是Vector支持线程同步，即同一时刻只允许一个线程对Vector进行写操作（新增、删除、修改），以保证多线程环境下数据的一致性，但需要频繁地对Vector实例进行加锁和释放锁操作，因此，Vector的读写效率在整体上比ArrayList低。

3．LinkedList：基于双向链表实现，增删快，查询慢，线程不安全

LinkedList采用双向链表结构存储元素，在对LinkedList进行插入和删除操作时，只需在对应的节点上插入或删除元素，并将上一个节点元素的下一个节点的指针指向该节点即可，数据改动较小，因此随机插入和删除效率很高。但在对LinkedList进行随机访问时，需要从链表头部一直遍历到该节点为止，因此随机访问速度很慢。除此之外，LinkedList还提供了在List接口中未定义的方法，用于操作链表头部和尾部的元素，因此有时可以被当作堆栈、队列或双向队列使用。

2.1.2 Queue

Queue是队列结构，Java中的常用队列如下。

◎ ArrayBlockingQueue：基于数组数据结构实现的有界阻塞队列。

◎ LinkedBlockingQueue：基于链表数据结构实现的有界阻塞队列。