八 Vector ArrayList LinkedList

1. Vector和Arraylist作为动态数组(使用对数组来保存, 数组已满时,会创建新的数组, 并拷贝原有数组数据. 前者每次扩容一倍, 后者每次增加50%), 其内部元素以数组形式存储, 所以非常适合随机访问,除了尾部的插入(不触发扩容的情况下)和删除,性能较差, 比如在中间位置插入一个元素,就需要移动后续所有的元素.

public boolean add(E e){
   ensureCapacity(size+1);//确保内部数组有足够的空间
   elementData[size++]=e;//将元素加入到数组的末尾，完成添加
   return true;      
} 
//不够通过grow增加
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1); //新容量为原来的1.5倍
        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);
    }

2. LinkedList 双向列表. 节点插入,删除高效的多

//LinkedlLIst的add方法实际调用下面的方法
 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. 排序算法
   排序算法