/**
* jdk8
* ArrayList：底层动态数组实现(未初始化指定数组长度)
* add():添加元素时，才初始化数组长度为10。容量不够时，动态扩容策略为： 原容量 + 原容量*0.5
* get():根据数组索引直接查询数组
* remove():根据索引查询数组，然后将其他数据进行前移，最后将最后的那个索引对应值置为Null,等待GC回收
*==================================================================================
* LinkedList: 底层双向链表实现
* Node(Node<E> prev, E element, Node<E> next) {
* this.item = element;
* this.next = next;
* this.prev = prev;
* }
*
* final Node<E> newNode = new Node<>(l, e, null);
* last = newNode;
* if (l == null)
first = newNode;
* else
* l.next = newNode;
*
* =================================================================
* add()方法添加过程：new Node(),将element存放在newNode中，newNode.prev 指向last节点
* newNode.next 指向null
* 判断last节点是否为空，若为null,则 first = last = newNode;
* 否则last.next执行newNode
*
* newNode.prev 绑定 last，last.next 绑定 newNode，实现双向绑定(双向链表)
*
*
* ================================================================
* add(index,element)方法添加过程：
* 判断index是否等于当前集合大小，若等于则直接类似add()方法添加
* 若不等于，则：
* 1、根据index查询将要插入位置的节点 Node node(index)
* 2、linkBefore(element, node(index));
* Node<E> succ = node(index);
*
* Node pred = succ.prev
*
* ******将newNode绑定在succ和succ.prev之间*************
* 将newNode.next = succ
* 将newNode.prev = pred;
*
* ---------将succ.prev，pred.next重新指向newNode，实现双向绑定------
* 将succ.prev = newNode
* 将pred.next = newNode
*
*
* public void add(int index, E element) {
* if (index == size)
* linkLast(element);
* else
* linkBefore(element, node(index));
* }
*
*
* // 找到新插入位置的节点的next或prev
* Node<E> node(int index) {
* // assert isElementIndex(index);
*
* if (index < (size >> 1)) {
* Node<E> x = first;
* for (int i = 0; i < index; i++)
* x = x.next;
* return x;
* } else {
* Node<E> x = last;
* for (int i = size - 1; i > index; i--)
* x = x.prev;
* return x;
* }
* }
*
*
* void linkBefore(E e, Node<E> succ) {
* // assert succ != null;
* final Node<E> pred = succ.prev;
* final Node<E> newNode = new Node<>(pred, e, succ);
* succ.prev = newNode;
* if (pred == null)
* first = newNode;
* else
* pred.next = newNode;
* size++;
* modCount++;
* }
*
* 综上：
* ArrayList：动态数组实现；对于指定位置的添加和删除操作之后，都会有移动元素操作。导致效率低下，而查询则根据索引直接定位，效率高
*
* LinkedList：双向链表实现，对于指定位置的添加和删除操作之后，只需要修改其位置节点执向即可，效率高。而查询则根据节点引用层层调用，效率低下
*
*/