集合之ArrayList

ArrayList的概念

ArrayList是一个支持快速访问、序列化、克隆的容器，底层数据结构由数组实现，动态扩容实质为数组的扩容。
ArrayList实现RandomAccess, Cloneable, java.io.Serializable接口，用于标记是否支持快速访问、序列化、克隆。

ArrayList实现与List接口，继承与AbstractList抽象类

ArrayList的总结

• 支持快速访问（随机访问）、查询快，修改慢
• 每次扩容大小为原来数组长度的1.5倍
• 拥有快速失败机制，如果在遍历中，删除元素，则立即抛出ConcurrentModificationException异常

ArrayList拥有三个构造方法

• 默认无参构造方法，将DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值给elementData，在第一次add操作的时候，将elementData的长度扩容到10.
• ArrayList(int initialCapacity) 构造器，可指定数组容量的大小，如果initialCapacity大于0，则根据initialCapacity初始化数组大小，如果initialCapacity为0，则EMPTY_ELEMENTDATA赋值给elementData，此处需要注意EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA的区别，DEFAULTCAPACITY_EMPTY_ELEMENTDATA在第一次添加的时候会扩容到10，而EMPTY_ELEMENTDATA却不会
• ArrayList(Collection<? extends E> c) 构造器，传入的是一个实现了Collection接口的集合类，这个地方的逻辑是如果这集合有元素，则将集合赋值给我们的elementData。如果没元素，则elementData=EMPTY_ELEMENTDATA

ArrayList的添加方法

点击查看代码

   public boolean add(E e) {
        //确保数组的大小是否满足，并进行扩容，增加modCount
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //将新的元素插入
        elementData[size++] = e;
        return true;
    }
 private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    /**
     * 确保数组的长度容量是否满足
     * @param minCapacity
     */
    private void ensureExplicitCapacity(int minCapacity) {
        //数组结构修改次数，如果在迭代中，此count与size不一致，则执行快速失败机制
        modCount++;

        // overflow-conscious code
        //判断当前数组的大小是否需要扩容
        if (minCapacity - elementData.length > 0)
            //进行扩容
            grow(minCapacity);
    }
  /**
     *
     *增加容量以确保它至少可以容纳由最小容量参数指定的元素数量。
     *
     * @param minCapacity 所需的最小容量
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        //获取原数组的大小
        int oldCapacity = elementData.length;
        //这里进行计算新的容量==》原容量+（原容量右移1位）==>10+(10/2)=15==》所以arrayList每次扩容是在原本的容量上扩容至原来的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //判断新容量扩容后是否能满足最新容量的需求
        //如果不满足，则新容量大小等于当前最小容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //新容量大于 最大数组长度的话，则
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            //将新容量设置为整形的最大值或MAX_ARRAY_SIZE
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        //将数组扩容，进行数组拷贝
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    public void add(int index, E element) {
        //范围检查
        rangeCheckForAdd(index);
        //扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //将数组元素从index拷贝（size-1）个元素到index+1的位置。空出当前index下标所在的位置
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

ArrayList的删除操作

点击查看代码

    public E remove(int index) {
        //检查是否越界
        rangeCheck(index);
        //修改操作增加
        modCount++;
        //获取要删除的元素
        E oldValue = elementData(index);
        //要移动的元素个数
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }