本文共 7093 字，大约阅读时间需要 23 分钟。
List接口在Collection的基础上添加了大量的方法，使得可以在List的中间插入和删除元素,并且存放的顺序与插入的顺序一致。
public interface Listextends Collection { // 查询操作 int size(); boolean isEmpty(); boolean contains(Object o); Iterator iterator(); // 修改操作 boolean add(E e); boolean remove(Object o); boolean containsAll(Collection c); boolean addAll(Collection c); boolean addAll(int index, Collection c); boolean removeAll(Collection c); boolean retainAll(Collection c); void clear(); // 基于位置的访问操作 E get(int index); E set(int index, E element); void add(int index, E element); E remove(int index); // 搜寻操作 int indexOf(Object o); int lastIndexOf(Object o); ListIterator listIterator(); ListIterator listIterator(int index); List subList(int fromIndex, int toIndex); ……}
List|------ArrayList|------Vector| |-------Stack|------LinkedList
ArrayList 是 List接口的一个实现类，可以说 ArrayList 是我们使用最多的 List 集合。从类名可以看出，ArrayList应该是基于数组而生成的，而事实确实如此，ArrayList的底层实现是基于动态数组而完成，保留了数组在存取元素方面的优势。
private static final int DEFAULT_CAPACITY = 10; private static final Object[] EMPTY_ELEMENTDATA = {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; transient Object[] elementData; private int size; private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 可以看出，ArrayList的默认容量为10，内部存储继承自Object的对象数组，如果使用无参构造函数时，使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA；如果为含参构造函数，使用EMPTY_ELEMENTDATA。elementData数组用来存储集合中的内容，数组的长度即为ArrayList的Capacity，有别于size属性，size表示当前ArrayList中保存的元素个数，数组的最大值为Integer.MAX_VALUE - 8。
LinkedList是双向链表，链表中的每个节点都包含了对前一个和后一个元素的引用。节点的数据结构如下：
private static class Node{ E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }
public class LinkedListextends AbstractSequentialList implements List , Deque , Cloneable, java.io.Serializable{ transient int size = 0; transient Node first; transient Node last; ……}
Vector的数据结构和ArrayList差不多，包含了3个成员变量：elementData，elementCount，capacityIncrement。
protected Object[] elementData; protected int elementCount; protected int capacityIncrement; private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; public Vector() { this(10); } elementData是Object[]的数组，初始大小为10，会不断的增长；elementCount是元素的个数；capacityIncrement是动态数组增长的系数。Stack继承至Vector，提供对数组末尾元素的新增、读取和删除操作。Vector与ArrayList最大差异在于Vector是线程安全的，而ArrayList不是。
ArrayList提供如下三种构造方法：
public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } public ArrayList(Collection c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } } 其中，使用ArrayList(int initialCapacity)和ArrayList()初始化后，elementData中没有元素，size为0，不过elementData的长度有可能不同。ArrayList(Collection c)将集合c转化为数组，然后检查转化的类型，如果不是Object[]类型，使用Arrays类中的copyOf方法进行复制；同时，如果c中没有元素，使用EMPTY_ELEMENTDATA初始化。
当使用诸如add(E)、add(int, E)、addAll(Collection)、addAll(int, Collection)等方法时存在扩容的可能性。ArrayList的扩容逻辑如下：
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } 简单来讲，扩容后的容量为原先容量的1.5倍，最小为原先值加1，最大为Integer.MAX_VALUE或者Integer.MAX_VALUE - 8。
LinkedList提供如下两种构造方法：
public LinkedList() { } public LinkedList(Collection c) { this(); addAll(c); } 默认从链表尾端新增元素，LinkedList由于结构特点，在新增节点时只要修改相关节点引用即可完成，因此并无特定扩容方式，从某种意义上讲，LinkedList无扩容之意义。
Vector提供如下四种构造方法：
public Vector(int initialCapacity, int capacityIncrement) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; this.capacityIncrement = capacityIncrement; } public Vector(int initialCapacity) { this(initialCapacity, 0); } public Vector() { this(10); } public Vector(Collection c) { elementData = c.toArray(); elementCount = elementData.length; // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, elementCount, Object[].class); } Stack的构造方法如下：
public Stack() { } Vector和Stack本质上都是数组，默认情况下都是在数组尾部新增元素。Vector构造方法接受一个带有扩容增量的参数，用于限定每次扩容的增量。
两者的扩容算法一致：
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); } 扩容量capacityIncrement小于等于0时，扩容后的容量为原先的2倍，如果大于0，则每次扩容大小为capacityIncrement，最小值最大值参考ArrayList。
ArrayList、LinkedList、Vector和Stack都实现了List接口，但是重写相关方法时逻辑不完全一样，笔者整理了如下差异：
| ArrayList | LinkedList | Vector、Stack | |
|---|---|---|---|
| add() | 默认情况下尾部新增，如果指定位置新增，则需要移动元素，甚至需要扩容 | 默认情况下尾部新增，如果指定位置新增，则需搜索指定位置完成新增，无需移动原先元素 | 同ArrayList相关处理逻辑 |
| remove() | 删除相关元素，同时移动后续元素，并调整capacity | 搜索相关元素，并修改相关元素引用为null，无需移动元素 | 同ArrayList相关处理逻辑 |
| get()、set() | 快速定位元素 | 遍历链表搜索 | 同ArrayList相关处理逻辑 |
| toArray() | 复制内部数组 | 遍历链表按照节点创建数组 | 同ArrayList相关处理逻辑 |
总体来说，ArrayList、Vector做插入、删除的时候，慢在数组元素的批量copy，快在寻址。同时，ArrayList的操作不是线程安全的！一般在单线程中才使用ArrayList，而在多线程中一般使用Vector或者CopyOnWriteArrayList。LinkedList做插入、删除的时候，慢在寻址，快在只需要改变前后Entry的引用地址。
本文比较详尽叙述了ArrayList、LinkedList和Vector之间的区别，涉及到的多线程安全问题，后续会有讲解，希望对读者有帮助。
转载地址：http://isgmi.baihongyu.com/