3.2 ArrayList、Vector和LinkedList的区别

List是一种线性的列表结构，它继承自Collection接口，是一种有序集合，List中的元素可以根据索引进行检索、删除或者插入操作。在Java语言中List接口有不同的实现类，图3-3给出了部分常用的List的实现类。

1）ArrayList是用数组实现的，数组本身是随机访问的结构。ArrayList为什么读取快？是因为get(int)方法直接从数组获取数据。为什么写入慢？其实这个说法并不准确，在容量不发生变化的情况下，它一样很快。当数组的容量不够用的时候，就需要扩容，而在容量被改变的时候，grow(int)方法会被调用，这个方法会对数组进行扩容扩从而导致写入数据的效率下降。

2）LinkedList是顺序访问结构，内部使用双向列表实现的。因此查询指定数据会消耗一些时间（需要遍历链表进行查询）。在头尾增加删除数据的操作非常迅速，但是如果要做随机插入，那么还是需要遍历，当然这还是比ArrayList的System.arraycopy性能要好一些。

3）Vector与ArrayList相比，Vector是线程安全的，而且容量增长策略不同。

4）Stack是Vector的子类，提供了一些与栈特性相关方法。

图3-3 List类图

ArrayList、Vector、LinkedList类均在java.util包中，都是可伸缩的数组，即可以动态改变长度的数组。

ArrayList和Vector都是基于存储元素的Object[] array来实现的，它们会在内存中开辟一块连续的空间来存储，由于数据存储是连续的，因此，它们支持用序号（下标）来访问元素，同时索引数据的速度比较快。但是在插入元素的时候需要移动容器中的元素，所以对数据的插入操作执行速度比较慢。ArrayList和Vector都有一个初始化的容量的大小，当里面存储的元素超过这个大小的时候就需要动态地扩充它们的存储空间。为了提高程序的效率，每次扩充容量的时候不是简单的扩充一个存储单元，而是一次就会增加多个存储单元。Vector默认扩充为原来的两倍（每次扩充空间的大小是可以设置的），而ArrayList默认扩充为原来的1.5倍（没有提供设置空间扩充的方法）。

ArrayList与Vector最大的区别就是synchronization(同步)的使用，没有一个ArrayList的方法是同步的，而Vector的绝大多数的方法（例如add、insert、remove、set、equals、hashcode等）都是直接或者间接同步的，所以Vector是线程安全的，ArrayList不是线程安全的。正是由于Vector提供了线程安全的机制，使其性能上也要略逊于ArrayList。

LinkedList是采用双向链表来实现的，对数据的索引需要从列表头开始遍历，因此在随机访问的效率比较低，但是插入元素的时候不需要对数据进行移动，因此插入效率较高。同时，LinkedList不是线程安全的。

那么，在实际使用时，如何从这几种容器中选择合适的使用？当对数据的主要操作为索引或只在集合的末端增加、删除元素，使用ArrayList或Vector效率比较高。当对数据的操作主要为指定位置的插入或删除操作，使用LinkedList效率比较高。当在多线程中使用容器时（即多个线程会同时访问该容器），选用Vector较为安全。