Table of Contents
Collection 是Java集合的一个根接口，内部仅仅做 add()，remove()，contains()，size() 等方法的声明。
List 接口是Collection接口的一个子类，在Collection基础上扩充了方法。同时可以对每个元素插入的位置进行精确的控制，它的主要实现类有 ArrayList，Vector，LinkedList。
1. ArrayList
ArrayList实现了List接口，它是基于数组的一个实现。
private static final int DEFAULT_CAPACITY = 10;
transient Object[] elementData;
这里可以看出，elementData提示了是基于数组的实现，DEFAULT_CAPACITY指名了默认容量为10个。
add()
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
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);
}
进行一个add()方法，首先通过ensureCapacityInternal(size + 1)判断需不需要扩容;如果ArrayList的大小已经不满足需求时，那么就将数组变为原长度的1.5倍，之后的操作就是把老的数组拷到新的数组里面。然后再进行 elementData[size++] = e。插入的时间复杂度O(1)，是非常高效的。如果在固定位置插入，那么代码：
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
从System.arraycopy()可以看出，这时候就是比较低效的了。
ArrayList 不适合 增删操作非常多的操作。首先可以看到这句话：elementData = Arrays.copyOf(...); 需要知道的是，Arrays.copyOf函数的内部实现是再创建一个数组，然后把旧的数组的值一个个复制到新数组中。当经常增加操作的时候，容量不够的时候，就会进行上述的扩容操作，这样性能自然就下来了。或者说，当我们在固定位置进行增删的时候，都会进行System.arraycopy(elementData, index, elementData, index + 1, size - index);也是非常低效的。
ArrayList 总结：
ArrayList 可以插入空值，也可以插入重复值
ArrayList 是基于数组的时候，所以很多数组的特性也直接应用到了ArrayList。
ArrayList 的性能消耗主要来源于扩容和固定位置的增删。
ArrayList 创建的时候需要考虑是否要初始化最小容量，以此避免扩容带来的消耗。
2. LinkedList
LinkedList不同于ArrayList和Vector，它是使用链表的数据结构，不再是数组。
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
当进行增删的时候，只需要改变指针，并不会像数组那样出现整体数据的大规模移动，复制等消耗性能的操作。
3. Vector
ArrayList不是线程安全的，Vector可以看作是ArrayList的一个线程安全版本也是实现了List接口。它和HashTable一样，是属于一种同步容器，而不是一种并发容器。
protected Object[] elementData;
public Vector() {
this(10);
}
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
可以看到，和ArrayList也是一样的，只是加了synchronized进行同步。
4. ArrayList，Vector，LinkedList 的整体对比
- 实现方式：
- ArrayList，Vector是基于数组的实现。
- LinkedList是基于链表的实现。
- 同步问题：
- ArrayList,LinkedList不是线程安全的。
- Vector是线程安全的，实现方式是在方法中加synchronized进行限定。
- 适用场景和性能消耗
- ArrayList和Vector由于是基于数组的实现，所以在固定位置插入，固定位置删除这方面会直接是 O(n)的时间复杂度，另外可能会出现扩容的问题，这是非常消耗性能的。
- LinkedList不会出现扩容的问题，所以比较适合增删的操作。但是由于不是数组的实现，所以在定位方面必须使用遍历的方式，这也会有O(n)的时间复杂度。
