ArrayList
JDK7：
ArrayList list = new ArrayLIst();在底层创建了长度为10 的Object[]数组elementData ；无参构造器默认10；
源码解析
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
list.add(123);//就等于在数组中下标0处加了一个值：elementData[0] = new Integer(123);
。。。
list.add(10);//elementData[10] = new Integer(10);
如果此次的添加导致底层elementData数组容量不够，大于或等于数组容量就会自动扩容。
默认情况下，扩容为原来的1.5倍，同时需要将原来的数组中的数据复制到新的数组中；
源码解析
/**
* Appends the specified element to the end of this list.//将指定的元素追加到列表的末尾。
*
* @param e element to be appended to this list//要追加到此列表的@param e元素
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
① ensureCapacityInternal方法名的英文大致是“确保内部容量”，size表示的是执行添加之前的元素个数，并非ArrayList的容量，容量应该是数组elementData的长度。ensureCapacityInternal该方法通过将现有的元素个数数组的容量比较。看如果需要扩容，则扩容。
②是将要添加的元素放置到相应的数组中。
源码解析
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
根据传入的最小需要容量minCapacity来和数组的容量长度对比，如果minCapacity大于或等于数组容量，则需要进行扩容
建议：使用带参数的构造器：ArrayList list = new ArrayList(int capacity);最好是10以上，不然还不如默认10个呢！
ArrayList扩容的核心方法grow()；
- 当前数组是由默认构造方法生成的空数组并且第一次添加数据。此时minCapacity等于默认的容量（10）那么根据下面逻辑可以看到最后数组的容量会从0扩容成10。而后的数组扩容才是按照当前容量的1.5倍进行扩容；
- 当前数组是由自定义初始容量构造方法创建并且指定初始容量为0。此时minCapacity等于1那么根据下面逻辑可以看到最后数组的容量会从0变成1。这边可以看到一个严重的问题，一旦我们执行了初始容量为0，那么根据下面的算法前四次扩容每次都 +1，在第5次添加数据进行扩容的时候才是按照当前容量的1.5倍进行扩容。
- 当扩容量（newCapacity）大于ArrayList数组定义的最大值后会调用hugeCapacity来进行判断。如果minCapacity已经大于Integer的最大值（溢出为负数）那么抛出OutOfMemoryError（内存溢出）否则的话根据与MAX_ARRAY_SIZE的比较情况确定是返回Integer最大值还是MAX_ARRAY_SIZE。这边也可以看到ArrayList允许的最大容量就是Integer的最大值（-2的31次方~2的31次方减1）。
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*增加容量，以确保它能容纳至少最小容量参数指定的元素数量。
*
* @param minCapacity the desired minimum capacity//想要的最小容量
*/
//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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
JDK8:
8中ArrayList的变化：
ArrayList list = new ArrayList();底层不会在自动创建数组，而是一个Object[] elementDat初始化为：{};并没有创建长度为10的数组；
list.add("哈哈");第一次调用add();的时候，底层才会创建长度为10的数组，并将数据 "哈哈" 添加到数组elementData中；后续添加与扩容与JDK7一样；
总结：JDK7中的ArrayList的对象创建类似于单例模式中的饿汉式，一次性添加；而JDK8中的ArrayList的对象的创建类似于单例模式中的懒汉式，需要的时候再创建延迟了数组的创建，节省了内存空间；
LinkedList
内部结构图：LinkedList内部是一个两端链接的双向链表；每个元素都会记录前一个元素和后一个元素
LinkedList list = new LinkedList(); 此刻，内部声明了一个Node类型的first和last属性，默认值为null；list.add(123); 此刻，将123封装到二楼Node中，创建了Node对象。
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;
}
}
LinkedList内部是一个双向链表结构，有两个变量，first指向链表头部，last指向链表尾部。size表示当前链表中的数据个数
transient int size = 0;
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
(第一个==空 并且 最后一个 == null) 或者 (第一个的上一个==空 并且 第一个的项 != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
添加元素 A：如果是第一个元素，那么它是头，也是尾；如果不是第一个元素，那么F前面的元素B指向F，F后面的元素C指向F;
删除：同理！
- 元素在内存中存储的时候是地址是无序的
- 但是元素之间是用链表链接起来的，元素在集合中是有序的
Vector
JDK7和JDK8中通过vector()构造器创建对象时，底层都创建了长度为10的数组，在扩容方面，默认为原数组的长度的2倍；
Vector出现在JDK1.0中，而List出现在JDK1.2中，List出现之后，Vector纳入了List集合；Vector已经过时，现在基本不用了。
