ArrayList和LinkedList（常用方法、底层结构及扩容机制）
1.ArrayList解说
ArrayList初始长度为0（这里以jdk1.8为例），是一个Object类型的空数组，如下
当第一次调用add后，长度变为10
当数组首次扩容的10个空间用完需要扩容后，会第二次走grow方法来扩容（每次扩容为1.5倍）
总的来说：
ArrayList初始大小为10，每次1.5倍进行扩容；它的底层是用数组实现的，所以查询速度相对LinkedList要快。
2.LinkedList解说
（1）* LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
* LinkedList 实现 List 接口，能对它进行队列操作。
* LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
* LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
* LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
* LinkedList 是非同步的。
由于它的底层是用双向链表实现的，所以它对元素的增加、删除效率要比ArrayList好；它是一个双向链表，没有初始化大小，也没有扩容的机制，就是一直在前面或者后面新增就好。
（2）LinkedList底层的数据结构是基于双向循环链表的，且头结点中不存放数据,如下：
private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;header是双向链表的头节点，它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量： previous, next, element。其中，previous是该节点的上一个节点，next是该节点的下一个节点，element是该节点所包含的值。size是双向链表中节点实例的个数。
总之，addBefore(E e,Entry<E> entry)实现在entry之前插入由e构造的新节点。而add(E e)实现在header节点之前插入由e构造的新节点。为了便于理解，下面给出插入节点的示意图。
