list 基本复习

ArrayList：
1：底层是数组结构。支持随机访问。
2：扩容机制：当前数组元素下标到达数组长度时，进行1.5倍扩容。

// 在grow函数中以1.5的速度扩容。
int newCapacity = oldCapacity + (oldCapacity >> 1);

LinkedList:
1:底层是个双端列表。不支持随机访问。增删快。不需要像ArrayList调用System.arraycopy（），实际操作的是node节点。不需要扩容。

2：获取数据:

// 操作对应节点的Item，相对于ArrayList多了一层node的引用。
public E get(int index) {
     this.checkElementIndex(index);
     return this.node(index).item;
}
// 二分查找
LinkedList.Node<E> node(int index) {
        LinkedList.Node x;
        int i;
        if (index < this.size >> 1) {
            x = this.first;
            for(i = 0; i < index; ++i) {
                x = x.next;
            }
            return x;
        } else {
            x = this.last;
            for(i = this.size - 1; i > index; --i) {
                x = x.prev;
            }
            return x;
        }
    }