List集合之ArrayList（一）通过源码看特性

逃离我推掉我的手 2023-10-04 09:00 2阅读 0赞

# 思维导图 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmY18xMjgyMjA_size_16_color_FFFFFF_t_70][]

***(以下源码来自jdk1.8.0\_282)***

# 数据结构 #

## elementData ##

/**
         * The array buffer into which the elements of the ArrayList are stored.
         * The capacity of the ArrayList is the length of this array buffer. Any
         * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
         * will be expanded to DEFAULT_CAPACITY when the first element is added.
         */
        transient Object[] elementData; // non-private to simplify nested class access

ArrayList容器的本质是一个Object[]类型的数组。
    
    即ArrayList容器存储的元素，本质都是存储在Object[]类型数组中。
    
    ArrayList中定义了实例变量 Object[] elementData 来作为底层数组。

# 构造器 #

## public ArrayList() ##

/**
         * Shared empty array instance used for default sized empty instances. We
         * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
         * first element is added.
         */
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
        
    
        /**
         * Constructs an empty list with an initial capacity of ten.
         */
        public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }

ArrayList无参构造器创建对象时，elementData固定赋值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
    
    其中DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个空的Object[]的数组。
    
    所以使用new ArrayList()得到的是一个空的Object[]的数组，且该空数组是一个特定对象DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

## public ArrayList(int initialCapacity) ##

/**
         * Shared empty array instance used for empty instances.
         */
        private static final Object[] EMPTY_ELEMENTDATA = {};
    
        /**
         * Constructs an empty list with the specified initial capacity.
         *
         * @param  initialCapacity  the initial capacity of the list
         * @throws IllegalArgumentException if the specified initial capacity
         *         is negative
         */
        public ArrayList(int initialCapacity) {
            if (initialCapacity > 0) {
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) {
                this.elementData = EMPTY_ELEMENTDATA;
            } else {
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            }
        }

ArrayList带一个int形参的构造器创建对象时，可以由外部指定一个初始容量initialCapacity。
    构造器内部根据initialCapacity来创建一个对应长度的数组。
    
    当initCapacity>0时，构造器内部正常创建一个new Obejct[initialCapacity]对象给elementData。
    当initCapacity=0时，构造器就将固定的EMPTY_ELEMENTDATA空Object[]数组赋值给elementData。
    当initCapacity<0时，构造器就抛出异常，因为数组的长度不能是负数。
    
    --------------------------------------------------------------------------------
    
    其中EMPTY_ELEMENTDATA也是一个空的Object[]数组。那么此处为什么不将DEFAULTCAPACITY_EMPTY_ELEMENTDATA给elementData呢？
    而要使用本质上重复的EMPTY_ELEMENTDATAn呢？
    
    虽然DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA都是空Object[]数组，
    但是它们的内存地址值不同，是两个不同的对象。
    而后面针对不同构造器初始化的elementData扩容时，会有不同的扩容方案。
    比如使用ArrayList()创建对象时，使用该无参构造器的人不确定要初始化的容器容量，
    可能很大，也可能很小，所以需要系统的扩容方案偏向折中。
    
    比如使用ArrayList(int initialCapacity)创建对象时，
    使用该构造器的人应该已经确切知道容器容量的大小了，
    所以就算后期数据超了事先预定的容器容量，也应该不会超过太多，
    所以需要系统的扩容方案偏向保守。
    
    但是不论是无参构造器，还是指定初始容器容量的构造器，都是有可能定义一个容量为0的容器的。
    所以为了后期扩容时，系统知道选择的是什么构造器，就给
    
    无参构造器专门定义了一个地址值固定的DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空Object[]数组。
    其它构造器定义了EMPTY_ELEMENTDATA的空Object[]数组。

## public ArrayList(Collection<? extends E> c) ##

public ArrayList(Collection<? extends E> c) {
            Object[] a = c.toArray();
            if ((size = a.length) != 0) {
                if (c.getClass() == ArrayList.class) {
                    elementData = a;
                } else {
                    elementData = Arrays.copyOf(a, size, Object[].class);
                }
            } else {
                // replace with empty array.
                elementData = EMPTY_ELEMENTDATA;
            }
        }

ArrayList带一个Collection实现类对象c的形参的构造器，该构造器创建对象，本质是将c中的元素转存到ArrayList容器中。
    
    首先需要判断c是否是空集合，如果是空集合，则直接创建一个空的ArrayList容器返回即可。
    这里底层elementData赋值为EMPTY_ELEMENTDATA。
    
    --------------------------------------------------------------------------------
    为什么这里不选择使用DEFAULTCAPCITY_EMPTY_ELEMENTDATA呢？
    
    我们需要知道DEFAULTCAPCITY_EMPTY_ELEMENTDATA是给容器容量不确定的情况使用的。
    而当前构造器是将一个已经存在的集合转成ArrayList集合，
    那么可以理解为要被转的集合是一个已知元素个数的数据源，
    那么我们要创建的ArrayList容器的容量就是已知的。所以选择了EMPTY_ELEMENTDATA。
    --------------------------------------------------------------------------------
    
    
    如果不是空集合，则说明c中有元素。那么就将c中的元素取出来存到新的ArrayList集合中就行了。
    
    以上是大致实现思路。但是具体实现如下：
    
    首先c.toArray()，将c转成的数组向上转型赋值给了Object[]数组a。
    
    然后通过判断a.length是否为0，来判断c集合中是否由元素，
    
    如果a.length == 0，则c中没有元素，那么就将elementData = EMPTY_ELEMENTDATA.
    如果a.length != 0,则c中有元素，那么就继续判断c的运行时类型是不是ArrayList,
    
    如果是，那么c.toArray()得到的返回值就是Object[]数组，
    那么就不需要新创建一个数组给elementData了。
    如果不是，那么c.toArray()得到的返回值就可能不是Object[]数组，
    那么就需要创建一个新的Object[]数组来转移c.toArray()数组中的元素后，赋值给elementData。
    
    这样新创建的ArrayList对象的底层数组elementData的初始化就完成了。

## 特性证明 ##

通过ArrayList构造器的实现，我们可以知道ArrayList的底层数据结构是数组，且是一个Object[]类型的数组。则可以证明特性
    
    集合元素类型可以不一致。证明：任何引用类型的元素都可以存入Object[]数组。
    
    集合元素类型只能是引用类型。证明：存入Obejct[]数组的元素类型只能是引用类型。
    
    集合元素只能是单列数据。证明：数组只能存单列数据。
    
    ArrayList元素有索引。证明：数组存储的元素都有索引。

# 插入元素 #

## public boolean add(E e) ##

/**
         * Appends the specified element to the end of this list.
         *
         * @param e element to be appended to this list
         * @return <tt>true</tt> (as specified by {@link Collection#add})
         */
        public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!! //ensureCapacityInternal用于对elementData数组进行扩容，传入的参数是扩容的最小容量，即size+1,即比当前elementData容量多一个元素的容量
            elementData[size++] = e;
            return true;
        }
    
        private void ensureCapacityInternal(int minCapacity) {
            ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));//calculateCapacity用于计算最适合elementData的扩容容量
        }
    
        private static int calculateCapacity(Object[] elementData, int minCapacity) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {// 当elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA时，说明elementData刚被new ArrayList()创建，而且当前是第一次add操作
                return Math.max(DEFAULT_CAPACITY, minCapacity);//由于此时minCapacity是size+1，即为1，而DEFAULT_CAPACITY是10，所以calculateCapacity方法返回10
            }
            return minCapacity;// 如果elementData!=DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则说明1.elementData是被new ArrayList()创建的,但当前不是第一次add操作 2.elementData不是被new ArrayLsit()创建的。  此时minCapacity就是size+1
        }
    
        private void ensureExplicitCapacity(int minCapacity) {
            modCount++; // modCount提示迭代器是否在迭代过程中有元素被增加或删除，若有，则快速失败
    
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)// ，minCapacity可能是size+1或者10，如果minCapacity - elementData.length<=0,则elementData数组无需扩容，否则需要扩容
                grow(minCapacity);
        }
    
        /**
         * Increases the capacity to ensure that it can hold at least the
         * number of elements specified by the minimum capacity argument.
         *
         * @param minCapacity the desired minimum capacity
         */
        private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;//将当前elementData数组长度定义为oldCapacity
            int newCapacity = oldCapacity + (oldCapacity >> 1);//定义扩容容量为newCapacity,且为oldCapacity的1.5倍
            if (newCapacity - minCapacity < 0)// 如果最小扩容容量 比 elementData数组长度的1.5倍还大，则将最小扩容容量作为最终扩容容量，否则就将老容量1.5倍，作为最终扩容容量
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)// 检查最终扩容容量是否比（int最大值-8）大
                newCapacity = hugeCapacity(minCapacity);// 如果是的话，则提供一个默认扩容容量
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);//最终将老的elementData数组中的数据复制到一个新的，容量为newCapacity的数组中，并最终赋值给elementData
        }
    
        private static int hugeCapacity(int minCapacity) {
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
        }
    
        @SuppressWarnings("unchecked")
        public static <T> T[] copyOf(T[] original, int newLength) {
            return (T[]) copyOf(original, newLength, original.getClass());
        }
    
        public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
            @SuppressWarnings("unchecked")
            T[] copy = ((Object)newType == (Object)Object[].class)
                ? (T[]) new Object[newLength]
                : (T[]) Array.newInstance(newType.getComponentType(), newLength);
            System.arraycopy(original, 0, copy, 0,
                             Math.min(original.length, newLength));
            return copy;
        }

add(E e)方法是在ArrayList尾部插入一个元素e。
    
    该方法有五部分逻辑
    1.计算最小扩容容量
    2.判断是否需要扩容
    3.计算实际扩容容量
    4.进行扩容
    5.扩容后add操作
    
    --------------------------------------------------------------------------
    
    1.计算最小扩容容量
    
    默认最小扩容容量就是当前elementData容量+1
    
    但是如果是new ArrayList()后，首次add操作，则最小扩容容量为10
    
    --------------------------------------------------------------------------
    
    2.判断是否需要扩容
    
    如果
    最小扩容容量 比 当前elementData的容量 小，则说明elementData容量是足够当前操作，即无需扩容。
    
    如果
    最小扩容容量 比 当前elementData的容量 大，则说明elementData容量不足，无法支持当前操作，需要立即扩容。
    
    --------------------------------------------------------------------------
    
    3.计算实际扩容容量（前提：第2步判断需要扩容）
    
    默认实际扩容容量 是 当前elementData容量的1.5倍。
    
    若 最小扩容容量 比 默认实际扩容容量 大，则说明默实际认扩容容量不足，则默认实际扩容容量需要改为最小容量的值。
    若 最小扩容容量 比 默认实际扩容容量 小，则说明默认实际扩容容量足够。
    
    继续比较默认实际扩容容量和MAX_ARRAY_SIZE的大小：
    如果默认实际扩容容量比MAX_ARRAY_SIZE还要大，
    则说明默认实际扩容容量已经超出了常规数组的最大容量，
    则再用最小扩容容量和MAX_ARRAY_SIZE比，
    若连最小扩容容量也比MAX_ARRAY_SIZE大，
    则实际扩容容量为Integer.MAX_VALUE，否则为MAX_ARRAY_SIZE。
    
    如果默认实际扩容容量比MAX_ARRAY_SIZE小，则实际扩容容量为默认实际扩容容量。
    
    --------------------------------------------------------------------------
    
    4.进行扩容
    
    Arrays.copyOf(elementData,实际扩容容量)
    
    System.arrayCopy(elementData,0,new Object[实际扩容容量]，0，elementData.length)；
    
    即将老数组elementData，从第0位开始,到第elementData.length-1位的元素  全部 复制到 新数组的第0位，到到第elementData.length-1位
    
    --------------------------------------------------------------------------
    
    5.扩容后add操作
    
    elementData[size++] = e;
    
    扩容前，elementData数组的最大索引是size-1,元素个数是size
    扩容后，elementData数组的最大索引至少是size,元素个数是size++
    
    所以扩容后add操作是elementData[size++] = e;

## public void add(int index, E element) ##

/**
         * Inserts the specified element at the specified position in this
         * list. Shifts the element currently at that position (if any) and
         * any subsequent elements to the right (adds one to their indices).
         *
         * @param index index at which the specified element is to be inserted
         * @param element element to be inserted
         * @throws IndexOutOfBoundsException {@inheritDoc}
         */
        public void add(int index, E element) {
            rangeCheckForAdd(index);
    
            ensureCapacityInternal(size + 1);  // 对数组进行扩容，和add(E e)扩容逻辑一致，注意该步该返回的数组是elementData = Arrays.copyOf(elementData,扩容后长度)，即elementData扩容了，且前xx位元素还是老的数组的元素
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);// 该步将elementData的index（插入索引位置）的元素，以及它后面的元素，全部往后挪了一位存储。这样就空出了index位置了
            elementData[index] = element;// 完成对index位置元素的插入
            size++;//完成元素个数的更新
        }
    
        /**
         * A version of rangeCheck used by add and addAll.
         */
        private void rangeCheckForAdd(int index) {
            if (index > size || index < 0)//由于底层数组的索引是[0,index-1],所以可以插入0（头部）,index（尾部），或(0,index)（中间）之间的位置，不能插入其他的位置
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

add(int index,E element)该方法是在ArrayList容器的index位置插入一个元素。
    
    其中index位置可以是当前容器的头部（0）,尾部（size）,或者中间（0~size）任意位置插入。
    
    该方法有六步
    1.index检查
    2.计算最小扩容容器
    2.判断是否需要扩容
    3.计算实际扩容容量
    4.进行扩容
    5.空出index位置
    6.插入元素到index位置
    
    其中2，3，4步和add(E e)方法一致。
    
    
    --------------------------------------------------------------------------------
    1.index检查
    
    插入元素的位置不能是头部之前的位置，也不能是尾部之后的位置
    
    所以 index >= 0 && index <= size
    
    --------------------------------------------------------------------------------
    2，3，4.进行扩容
    
    举个例子：
    扩容前，elementData.length,即容器容量为3，存储的元素为{1，2，3}，现在要在索引1处插入1.5元素。
    
    由于此时minCapacity=4 , minCapacity>elementData.length,所以需要进行扩容
    
    默认扩容大小为3+3*0.5 = 4，所以就扩容到4，并将老数组中元素按照索引位置转移到新数组中
    
    elementData = Arrays.copyOf(elementData,4);
    
    即扩容后的新数组为：
    elementData = {1，2，3，null}
    
    --------------------------------------------------------------------------------
    5.空出index位置
    
    System.arraycopy(elementData,index,elementData,index+1,size-index)
    
    此时 size还没有改变，还是老数组的元素个数，即3。
         index是要插入的索引位置，即为1。
    
    System.arraycopy(elementData,1,elementData,2,2);
    该步操作后，elementData的数组变为
    {1,2,2,3}
    
    --------------------------------------------------------------------------------
    6.插入元素到index位置
    
    elementData[index] = element;后即完成插入操作
    
    elementData = {1,1.5,2,3}

## public boolean addAll(Collection<? extends E> c) ##

/**
         * Appends all of the elements in the specified collection to the end of
         * this list, in the order that they are returned by the
         * specified collection's Iterator.  The behavior of this operation is
         * undefined if the specified collection is modified while the operation
         * is in progress.  (This implies that the behavior of this call is
         * undefined if the specified collection is this list, and this
         * list is nonempty.)
         *
         * @param c collection containing elements to be added to this list
         * @return <tt>true</tt> if this list changed as a result of the call
         * @throws NullPointerException if the specified collection is null
         */
        public boolean addAll(Collection<? extends E> c) {
            Object[] a = c.toArray();//将c转成数组
            int numNew = a.length;
            ensureCapacityInternal(size + numNew);  // Increments modCount// 最小扩容容量=当前数组容量+c集合元素个数
            System.arraycopy(a, 0, elementData, size, numNew);// 将c中元素复制到新数组的尾部
            size += numNew;//ArrayList集合元素个数变为size+numNew
            return numNew != 0;
        }

addAll(Collection c)
    该方法是ArrayList重写了List接口的抽象方法addAll(Collection c)。
    
    该方法含义是将c集合中的元素按顺序插入到调用者ArrayList集合的尾部。
    
    具体实现逻辑和add(E e)大致相同。只是add(E e)是只添加一个元素，而add(Collection c)是添加多个元素。

## public boolean addAll(int index, Collection<? extends E> c) ##

/**
         * Inserts all of the elements in the specified collection into this
         * list, starting at the specified position.  Shifts the element
         * currently at that position (if any) and any subsequent elements to
         * the right (increases their indices).  The new elements will appear
         * in the list in the order that they are returned by the
         * specified collection's iterator.
         *
         * @param index index at which to insert the first element from the
         *              specified collection
         * @param c collection containing elements to be added to this list
         * @return <tt>true</tt> if this list changed as a result of the call
         * @throws IndexOutOfBoundsException {@inheritDoc}
         * @throws NullPointerException if the specified collection is null
         */
        public boolean addAll(int index, Collection<? extends E> c) {
            rangeCheckForAdd(index);
    
            Object[] a = c.toArray();
            int numNew = a.length;
            ensureCapacityInternal(size + numNew);  // Increments modCount // 最小扩容容量 = 当前数组容量 + c集合中的元素个数
    
            int numMoved = size - index;
            if (numMoved > 0)
                System.arraycopy(elementData, index, elementData, index + numNew,
                                 numMoved);
    
            System.arraycopy(a, 0, elementData, index, numNew);
            size += numNew; // 插入后，ArrayList集合元素的个数变为size+numNew
            return numNew != 0;
        }

addAll(int index, Collection c)
    
    该方法是ArrayList重载的方法。
    
    该方法含义是在当前ArrayList集合的index索引处，插入c集合中的元素。
    
    该方法实现方案和add(int index,E e)大致一致。

## 特性证明 ##

add(E e)
    add(int index,E e)
    
    两个方法的实现证明了，ArrayList的集合元素是基于索引操作的，所以
    
    1.ArrayList集合元素是有索引的。
    
    且这两个方法实现类动态扩容，即证明
    
    2.ArrayList集合的长度是可变的
    
    另外，在add元素时没有特别检查元素本身是否重复
    
    3.ArrayList集合的元素是可重复的
    
    其次，add(E e)操作插入的元素，是将元素插入到当前底层数组的尾部
         add(int index,E e)是将元素插入到底层数组指定索引处。
    
    且元素取出的顺序就是插入的顺序，所以，证明：
    
    4.ArrayList集合的元素是有序的

# 删除元素 #

## public E remove(int index) ##

/**
         * Removes the element at the specified position in this list.
         * Shifts any subsequent elements to the left (subtracts one from their
         * indices).
         *
         * @param index the index of the element to be removed
         * @return the element that was removed from the list
         * @throws IndexOutOfBoundsException {@inheritDoc}
         */
        public E remove(int index) {
            rangeCheck(index);//检查要删除的索引是否合法，要删除的索引必须是elementData已有元素的索引
    
            modCount++;
            E oldValue = elementData(index);// 获取要删除索引上的元素，该方法执行完后需要返回被删除的元素
    
            int numMoved = size - index - 1;// （假设已经删除了索引上的元素，那么被删除索引后面的元素，需要自动往前挪动一位），这里numMoved是指有几个元素需要挪动。理解：要删除index位置的元素，那么index+1到size-1位置上元素，要往前挪，则一共有size-1-index个元素需要挪动位置
            if (numMoved > 0)
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);//进行挪位，即将elementDat中从index+1位置开始的numMoved个元素，复制到elementData中的index位置开始的numMoved个元素的位置上
            elementData[--size] = null; // clear to let GC do its work//由于元素都往前挪动了一位，所以理论上数组的最后一个元素应该是空的，所以这里将elementData[size-1]的元素设置为了null。另外size是指集合的元素个数，而由于已经删除了一个元素，所以--size
    
            return oldValue;// 返回删除操作前，保留的被删除的元素，告诉外部删除了哪个元素
        }
    
        /**
         * Checks if the given index is in range.  If not, throws an appropriate
         * runtime exception.  This method does *not* check if the index is
         * negative: It is always used immediately prior to an array access,
         * which throws an ArrayIndexOutOfBoundsException if index is negative.
         */
        private void rangeCheck(int index) {
            if (index >= size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    
        @SuppressWarnings("unchecked")
        E elementData(int index) {
            return (E) elementData[index];
        }

remove(int index)
    删除集合中指定索引处元素。即删除底层数组中指定索引处的元素。
    
    具体实现：
    
    1.检查需要删除元素的index是否合法
    2.计算挪位数
    3.进行挪位
    4.挪位后，将尾部多余元素设置为null
    5.更新size，即更新集合元素个数
    -----------------------------------------------------------------------------------
    
    关于挪位实现：
    
    举个例子：当前有数组 Objetc[] arr = {1,2,3,4,5,6};
    
    现在需要把索引1处的元素删除，且索引2处的元素自动填补到被删除的索引1处，索引3自动填补到索引2，...
    
    即：删除索引1位置元素后：
    
    {1，null,3,4,5,6}
    
    挪位后
    
    {1,3,4,5,6,null}
    理论上应该这样实现。但是这样实现不符合最简代码逻辑。
    
    -----------------------------------------------------------------------------------
    
    关于挪位实现：
    
    真实实现逻辑：
    当前有数组 Objetc[] arr = {1,2,3,4,5,6};
    现在想把arr中索引1处的元素删除。其实代码实现删除的方式有很多中，覆盖了该索引处元素也算是删除。
    
    System.arraycopy(arr,2,arr,1,4)
    
    这行代码即可实现对索引1处元素的覆盖，即删除。
    
    代码含义是：将arr数组从索引2开始的4个元素，复制到arr数组从索引1开始的4个元素中。
    
    即可实现挪位，即将被删除索引1处后面的元素，自动往前面移动一位。
    
    这行代码的运行结果是：
    
    arr = {1,3,4,5,6,6}
    
    这样的结果显然不符合要求，因为虽然已经删除了索引1处的元素，并已经将删除元素后面的元素自动往前挪动了一位。但是挪动后，数组的最后一个元素显得有点突兀，
    
    因为我们期望删除索引1后的数组是{1,3,4,5,6}或者是{1,3,4,5,6,null}
    
    最简单解决方案就是，我们直接将arr[size-1]元素设置为null，即数组最后一个元素设置为null。

## public boolean remove(Object o) ##

/**
         * Removes the first occurrence of the specified element from this list,
         * if it is present.  If the list does not contain the element, it is
         * unchanged.  More formally, removes the element with the lowest index
         * <tt>i</tt> such that
         * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
         * (if such an element exists).  Returns <tt>true</tt> if this list
         * contained the specified element (or equivalently, if this list
         * changed as a result of the call).
         *
         * @param o element to be removed from this list, if present
         * @return <tt>true</tt> if this list contained the specified element
         */
        public boolean remove(Object o) {
            if (o == null) {//如果要删除的元素为null，则循环遍历集合找到第一个null元素，并删除。另外由于null无法调用equals方法，所以无法和下面o!=null的情况合并处理
                for (int index = 0; index < size; index++)
                    if (elementData[index] == null) {
                        fastRemove(index);
                        return true;
                    }
            } else {//如果要删除的元素不为null，则循环遍历集合找到第一个符合equals检查的元素，并删除
                for (int index = 0; index < size; index++)
                    if (o.equals(elementData[index])) {// 注意此处判断元素相同是用的equals，所以如果数组元素是自定义类型，我们需要重写元素类型的类的equals方法，否则remove操作可能达不到要求
                        fastRemove(index);
                        return true;
                    }
            }
            return false;
        }
    
    
        /*
         * Private remove method that skips bounds checking and does not
         * return the value removed.
         */
        private void fastRemove(int index) {// 挪位实现，和前面remove(int index)实现思路一致
            modCount++;
            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
        }

remove(Object o)
    
    指删除集合中第一个和o相同的元素。
    
    挪位实现思路和remove(int index)实现一致。
    但是比remove(int index)多了寻找删除元素索引的逻辑。即挪位前要遍历出已有元素中第一个和o相同的元素，以期获得该元素的索引。
    
    所以remove(Object o)的实现需要关注o的运行时类型的equals方法是否需要重写。一般自定义类型需要重写。

## public boolean removeAll(Collection<?> c) ##

/**
         * Removes from this list all of its elements that are contained in the
         * specified collection.
         *
         * @param c collection containing elements to be removed from this list
         * @return {@code true} if this list changed as a result of the call
         * @throws ClassCastException if the class of an element of this list
         *         is incompatible with the specified collection
         * (<a href="Collection.html#optional-restrictions">optional</a>)
         * @throws NullPointerException if this list contains a null element and the
         *         specified collection does not permit null elements
         * (<a href="Collection.html#optional-restrictions">optional</a>),
         *         or if the specified collection is null
         * @see Collection#contains(Object)
         */
        public boolean removeAll(Collection<?> c) {
            Objects.requireNonNull(c);// c集合不能为null,否则报错空指针异常
            return batchRemove(c, false);// 删除当前ArrayList集合中和c集合的交集部分元素
        }
    
    
        private boolean batchRemove(Collection<?> c, boolean complement) {
            final Object[] elementData = this.elementData;// 获取当前ArrayList的底层数组
            int r = 0, w = 0;//定义初始变量，其中r用于遍历elementData,w用于记录非交集部分元素
            boolean modified = false;
            try {
                for (; r < size; r++)
                    if (c.contains(elementData[r]) == complement) // 如果ArrayList的r索引处元素是非交集元素，则将该元素存入只保留了交集元素的elementData数组中（注意此处是同一个数组elementData,一边判断数组元素是否非交集，一边将非交集元素再次覆盖存入数组中。由于是判断在前，覆盖在后，所以不会产生冲突。）
                        elementData[w++] = elementData[r];
            } finally {
                // Preserve behavioral compatibility with AbstractCollection,
                // even if c.contains() throws.
                if (r != size) {// r只是普通循环变量，一般而言上面for循环中如果没有异常发生，r==size总是true,除非发生异常才有可能r!=size。此时，处理方案是：保留elementData数组中已经排查出来的非交集元素0~w-1，也保留未排查部分r~size-1。注意未排查部分是r~size-1,而不是w~size,因为我们是从0~r之间排查出了w个非交集元素，并覆盖存入0~w-1。而在排查r索引处元素时，发生异常，则r本身没有排查完，所以一共还有size-1-r+1个元素没有排查
                    System.arraycopy(elementData, r,
                                     elementData, w,
                                     size - r);
                    w += size - r;
                }
                if (w != size) {// 正常情况try中的循环完成后，r==size总是true，所以继续判断非交集元素个数w，如果w==size，说明ArrayList集合元素全是非交集元素，则无需任何修改。如果w!=size,则说明ArrayList集合元素有部分交集元素
                    // clear to let GC do its work
                    for (int i = w; i < size; i++)// 由于elementData的0~w-1部分已经被非交集元素覆盖，所以只需要将w~size部分的交集元素设置为null，即可做到删除交集元素的功能。
                        elementData[i] = null;
                    modCount += size - w;
                    size = w;//而此时ArrayList集合元素个数，就是非交集元素个数w
                    modified = true;
                }
            }
            return modified;
        }

remove(Collection c)
    
    该方法是ArrayList重写List接口中定义的remove(Collection c)方法
    
    该方法含义是将ArrayList集合和c集合的交集元素全部删除。
    
    在remove动作前，校验了c不能为null，否则抛出空指针异常。
    
    ----------------------------------------------------------------------------------
    
    之后调用private boolean batchRemove(Collection<?> c, boolean complement)
    
    batchRemove是ArrayList类的私有工具方法。它主要是用来给removeAll,retainAll这两个公有方法使用。
    
    它的功能是：只删除(false)或只保留(true) 当前ArrayList集合中  和c集合有交集的元素。
    
    
    removeAll调用的是batchRmove(c,false);
    即只删除当前ArrayList集合中和c集合有交集的元素。
    
    batchRemove的具体实现解释，请看上面代码走读注释

# 思考题 #

## 1、分别计算下new ArrayList(),new ArrayList(0)，前五次扩容的容量值 ##

当new ArrayList()时，elementData初始容量是0。
    
    第一次扩容到10
    
    第二次扩容到10+10*0.5 = 15
    
    第三次扩容到15+15*0.5 = 22
    
    第四次扩容到22+22*0.5 = 33
    
    第五次扩容到33+33*0.5 = 49
    
    ---------------------------------------------------------------------------------------
    
    当new ArrayList(0)时，elementDat初始容量是0.
    
    第一次扩容到1
    
    第二次：minCapa=2,minCapa>ele.length,defCapa=1,min>def,所以最终扩容到2
    
    第三次：minCapa=3,minCapa>ele.length,defCapa=3,min=def,所以最终扩容到3
    
    第四次：minCapa=4,minCapa>ele.length,defCapa=4,min=def,所以最终扩容到4
    
    第五次：minCapa=5,minCapa>ele.length,defCapa=6,min<def,所以最终扩容到6

## 2、请仿照ArrayList的add(E e)实现对数组扩容一位，并在扩容后数组尾部插入一个元素。 ##

import java.util.Arrays;
    
    public class Main{
    	public static void main(String[] args){
    		Object[] arr = {1,2,3,4,5,6};
    		
    		//方式一
    		Object[] arrNew = Arrays.copyOf(arr,7);
    		System.out.println(Arrays.toString(arrNew));
    		
    		//方式二
    		Object[] arrNew2 = new Object[7];
    		System.arraycopy(arr,0,arrNew2,0,Math.min(arr.length,arrNew2.length));
    		System.out.println(Arrays.toString(arrNew2));
    	}
    }

ArrayList的add(E e)方法就是使用Arrays.copyOf(原数组，新数组长度)，而Arrays.copyOf的底层就是System.arraycopy(原数组，0,new Obejct[新数组长度]，0，Math.min(原数组长度，新数组长度))

## 3、请仿照ArrayList的add(int index,E e)实现对数组扩容一位，并在扩容后数组任意位置插入一个元素 ##

import java.util.Arrays;
    
    public class Main{
    	public static void main(String[] args){
    		// 将arr扩容为7
    		Object[] arr = {1,2,3,4,5,6};
    		Object[] arrNew = Arrays.copyOf(arr,7);
    		System.out.println(Arrays.toString(arrNew));//[1, 2, 3, 4, 5, 6, null]
    		
    		// 空出索引1位置
    		System.arraycopy(arrNew,1,arrNew,2,5);// 将arrNew从索引1开始往后5位元素，存储到arrNew的索引2开始的往后5位。
    		System.out.println(Arrays.toString(arrNew));//[1, 2, 2, 3, 4, 5, 6]
    		
    		// 插入元素到索引1位置
    		arrNew[1] = 1.5;
    		System.out.println(Arrays.toString(arrNew));//[1, 1.5, 2, 3, 4, 5, 6]
    	}
    }

ArrayList的add((int index,E element)方法的插入任意索引实现方法就是如上代码

## 4、ArrayList集合remove操作后，会对底层数组进行缩容吗？为什么? ##

不会。
    
    ArrayList集合remove操作后，会在原数组上执行
    
    System.arraycopy(elementData,index+1,elementData,index,size-index-1)
    
    这样操作后，elementData的长度并不会减少，或者说elementData并没有改变指向的数组对象，只是数组对象的内部元素改变了。
    
    
    ------------------------------------------------------------------------------------
    
    为什么不进行缩容操作？
    
    首先：我们需要明确一点，是没有“动态数组”这种数据结构的，动态数组只是一种概念。
    
    所以不论是数组扩容还是缩容，都是创建一个新容量的数组来承接老数组的元素。
    
    对于插入操作而言，如果数组容量不够了，则必须要进行扩容，否则无法执行插入操作。
    
    但是对于删除操作而言，
    删除元素只会让数组的容量更加富裕，而刻意的去缩容的话，
    需要创建新的数组，浪费性能和内存，
    而且万一后续操作又要插入元素，那么就又要重复扩容，得不偿失。

## 5、请思考下面代码运行结果（ArrayList的remove(Object o)方法考查） ##

import java.util.ArrayList;
    
    public class Main{
    	public static void main(String[] args){
    		ArrayList al = new ArrayList();
    		
    		Integer i1 = 127;
    		Integer i2 = new Integer(127);
    		
    		al.add(i1);
    		al.add(i2);
    		
    		al.remove(i2);
    		
    		System.out.println(al.size());
    		System.out.println(al.get(0) == i1);
    	}
    }

al中添加的i1,i2是两个不同地址值，但是相同内容的引用类型数据。
    
    ArrayList的remove(Object o)方法删除的是 (如果o非null)集合中第一个o.equals(elementData[index])==true的索引位置的元素。
    
    所以虽然al.remove(i2)中，al指定删除了i2,但是由于i2.equals(i1),所以al底层删除的其实是i1。
    
    所以al只剩下i2元素。则必然i2!=i1。

## 6、我们知道remove(Object o)只能删除调用者集合对象中第一个和o相同的元素，那么如果做到将和o相同的所有元素删除掉呢？ ##

import java.util.ArrayList;
    import java.util.Collections;
    
    public class Main{
    	public static void main(String[] args){
    		ArrayList al = new ArrayList();
    		
    		Collections.addAll(al,1,2,3,4,4,4,4,4,4,4,4,4,4);
    		
    		ArrayList repeat = new ArrayList();
    		repeat.add(4);
    		al.removeAll(repeat);
    		System.out.println(al);
    	}
    }

removeAll(Collection c)
    
    可以删除调用者ArrayList集合对象中和c集合有交集的所有元素。
    
    所以也可以用来和remove(E e)互相辅佐。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmY18xMjgyMjA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210328231257133.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmY18xMjgyMjA=,size_16,color_FFFFFF,t_70