ArrayList源码详解

阳光穿透心脏的1/2处 2022-04-25 09:30 224阅读 0赞

### 文章目录 ###

*  List分析
 *   *  List接口所有代码
     *  List核心代码
     *  AbstractList：减少实现List所需精力
 *  ArrayList源码解析
 *   *  ArrayList的知识
     *  ArrayList的内部结构
     *   *  ArrayList的初始化
         *  ArrayList的改操作
         *  ArrayList的查询元素
         *  ArrayList 删除元素
         *  ArrayList的增加
         *  ArrayList实现Collection中的一些必要方法
     *  ArrayList全部代码
     *  ArrayList总结

# List分析 #

[ArrayList和LinkedList分析][ArrayList_LinkedList]

我在这里贴出我翻译后的List接口内容；

所有标注可选的方法都是不强制要求去实现的方法。

> 如果不愿意详细阅读Java的List源码，我在下面还提供了其中最核心的方法。

## List接口所有代码 ##

import java.util.*;
    import java.util.function.UnaryOperator;
    
    /** * List接口属于集合类，要继承Collection接口 * * @param <E> 泛型，以便于更好的对对象进行操作. */
    public interface List<E> extends Collection<E> { 
        // 查询操作
    
        /** * 返回List的容量 * * @return size，将List中的元素个数返回; */
        @Override
        int size();
    
        /** * 判断是否这个List中没有任何元素 * * @return <tt>true</tt> 如果这个List中没有任何元素 */
        @Override
        boolean isEmpty();
    
        /** * List中是否包含这个Object，如果是则返回<tt>true</tt> * * @param o 查询的object * @return 如果List中包含，则<tt>true</tt> */
        @Override
        boolean contains(Object o);
    
        /** * 以适当的顺序返回此列表中元素的迭代器。 * * @return 以适当的顺序返回此列表中元素的迭代器。 */
        @Override
        Iterator<E> iterator();
    
        /** * 返回一个包含此列表中所有元素的数组 * 注意：这里返回的数组对象应该是'安全'的，也就是不能引用List中任何的实现，必须新建一个数组并返回。 * <p>此方法充当基于数组和基于集合的API之间的桥梁。</p> * * @return 一个包含此列表中所有元素的数组 * @see Arrays#asList(Object[]) */
        @Override
        Object[] toArray();
    
        /** * 如果传入的数组足够容纳，则放入a中并返回a； * 如果不足以容下，那么依然return toArray()方法 * * @param a 结果数组，但是只作为参考，如果容量不足，则依然不会使用 * @return T[] */
        @Override
        <T> T[] toArray(T[] a);
    
        /** * 将指定的元素追加到此列表的末尾（可选 * * @param e 待添加元素 * @return 添加成功则<tt>true</tt> */
        // 修改操作
        @Override
        boolean add(E e);
    
        /** * 从此List中删除第一次出现的指定元素 * * @param o 待删除元素 * @return 删除成功则<tt>true</tt> */
        @Override
        boolean remove(Object o);
    
        // 批量修改操作
    
        /** * 如果此列表包含指定集合的所有元素，则返回<tt>true</ tt>。 * * @param c 指定集合 * @return 全部都被包含，返回<tt>true</tt> */
        @Override
        boolean containsAll(Collection<?> c);
    
        /** * 将指定集合中的所有元素追加到此列表的末尾，按照其对应的迭代器返回的顺序（可选。 * 是否可以修改传入的集合对象，应由接口实现人去规定，这里我们不做强制要求。 * * @param c 指定待添加元素们对应的集合容器 * @return 添加成功则返回<tt>true</tt> */
        @Override
        boolean addAll(Collection<? extends E> c);
    
        /** * 在上面的addAll的基础上，将新加入元素从第index - 1个位置开始存储. * * @param index 新增元素放入的开始下标 * @param c 指定待添加元素们对应的集合容器 * @return 添加成功则返回<tt>true</tt> */
        boolean addAll(int index, Collection<? extends E> c);
    
        /** * 从此列表中删除指定集合中包含的所有元素（可选。 * * @param c 待删除元素的集合 * @return <tt>true</tt> */
        boolean removeAll(Collection<?> c);
    
        /** * 求交集，将交集中的元素保留，其余元素删除（可选。 * * @param c 待删除元素的集合 * @return <tt>true</tt> */
        boolean retainAll(Collection<?> c);
    
        /** * 将此运算符的每个元素替换为将运算符应用于该元素的结果。 * 运算符抛出的错误或运行时异常被转发给调用者 * * @param operator 运算符应用于每个元素 */
        default void replaceAll(UnaryOperator<E> operator) { 
            Objects.requireNonNull(operator);
            final ListIterator<E> li = this.listIterator();
            while (li.hasNext()) { 
                li.set(operator.apply(li.next()));
            }
        }
    
        /** * List的sort默认实现，如果实现了List接口的类没有实现sort()方法，则调用这个默认的方法. * * @param c 对象的比较器 */
        @SuppressWarnings({ "unchecked", "rawtypes"})
        default void sort(Comparator<? super E> c) { 
            Object[] a = this.toArray();
            Arrays.sort(a, (Comparator) c);
            ListIterator<E> i = this.listIterator();
            for (Object e : a) { 
                i.next();
                i.set((E) e);
            }
        }
    
        /** * 从此列表中删除所有元素（可选操作）。 * 此调用返回后列表将为空。 */
        void clear();
    
        // 比较和散列相关的方法
    
        /** * 当且仅当传入Object为list实现，且两者含有顺序相同的相同元素序列时为<tt>true</tt> * * @param o 传入Object，如果没有实现List接口，则抛出异常. * @return <tt>true<tt/> */
        boolean equals(Object o);
    
        /** * 求List的散列值 * * @return int */
        int hashCode();
    
        // 与位置访问相关的操作
    
        /** * 对应于数组操作的 * E obj = arr[index]; * * @param index 对应下标 * @return 返回下标对应的元素 */
        E get(int index);
    
        /** * 对应数组操作的 * arr[index] = element; * * @param index 对应下标 * @param element 对应值 * @return 返回之前在index位置的元素 */
        E set(int index, E element);
    
        /** * 将element元素插入到index位置，而[index,size- 1]得元素向后移动一位. * * @param index 对应下标 * @param element 对应值 */
        void add(int index, E element);
    
        /** * 将index对应得元素删除，其之后所有元素向前一步走。 * * @param index 对应下标 * @return 删除得元素值 */
        E remove(int index);
    
        // 搜索操作
    
        /** * 找到o 在List中第一次出现的位置，找不到就返回 -1 * * @param o 待查找元素 * @return 如果找到，返回下标，没找到，则-1 */
        int indexOf(Object o);
    
        /** * 从后向前找，于indexOf其他相同，除了查找方向 * * @param o 待查找元素 * @return 如果找到，返回下标，没找到，则-1 */
        int lastIndexOf(Object o);
    
        /** * 返回此列表中元素的列表迭代器（以一种合适的序列）。 * * @return 此列表中元素的列表迭代器（以一种合适的序列）。 */
        ListIterator<E> listIterator();
    
        /** * 从列表中的指定位置开始，返回此列表中元素的列表迭代器（以一种合适的序列）。 * * @param index 指定位置 * @return 从列表中的指定位置开始，返回此列表中元素的列表迭代器（以一种合适的序列）。 */
        ListIterator<E> listIterator(int index);
    
        // 视图操作
    
        /** * 得到子序列 * * @param fromIndex 开始下标(含) * @param toIndex 结束下标(不含) * @return List */
        java.util.List<E> subList(int fromIndex, int toIndex);
    
        /** * Java8新特性，有兴趣的可以自行搜索，本文不讲. * @since 1.8 */
        @Override
        default Spliterator<E> spliterator() { 
            return Spliterators.spliterator(this, Spliterator.ORDERED);
        }
    }

## List核心代码 ##

省去了许多不怎么核心的方法代码后，List接口中核心操作有：

public interface ListInterface<T> { 
        public void add(T val);
     
        public void add(Integer index, T val);
     
        public T remove(int index);
     
        public void clear();
     
        public T replace(int index, T val);
     
        public T getEntry(int index);
     
        public T[] toArray();
     
        public boolean contains(T anEntry);
     
        public int getLength();
     
        public boolean isEmpty();
    }

## AbstractList：减少实现List所需精力 ##

当然Java设计人员也发现了List接口中需要实现的方法过多导致实现出来的类有许多不使用的方法，所以Java设计人员提供了一个抽象类帮助减少无用方法，让程序员各取所需.

package unit2;
    
    import java.util.*;
    import java.util.List;
    
    /** * 此类提供{@link List} 接口的骨干实现， * 以最大限度地减少实现此接口所需的工作 */
    
    public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> { 
        /** * 唯一的构造器. （为了方便子类） */
        protected AbstractList() { 
        }
    
        /** * 将指定的元素追加到此列表的末尾（可选 * * @param e 待添加元素 * @return 添加成功则<tt>true</tt> */
        public boolean add(E e) { 
            add(size(), e);
            return true;
        }
    
        /** * get方法由子类自由发挥. */
        abstract public E get(int index);
    
        /** * set 可以自行实现，也可以不支持这个操作. */
        public E set(int index, E element) { 
            throw new UnsupportedOperationException();
        }
    
        /** * 可以自行实现，也可以不支持这个操作. */
        public void add(int index, E element) { 
            throw new UnsupportedOperationException();
        }
    
        /** * 可以自行实现，也可以不支持这个操作. */
        public E remove(int index) { 
            throw new UnsupportedOperationException();
        }
    
        // Search Operations
    
        /** * 通过 Iterator 遍历找到第一个出现都的o,如果没出现则-1 */
        public int indexOf(Object o) { 
            ListIterator<E> it = listIterator();
            if (o == null) { 
                while (it.hasNext())
                    if (it.next() == null)
                        return it.previousIndex();
            } else { 
                while (it.hasNext())
                    if (o.equals(it.next()))
                        return it.previousIndex();
            }
            return -1;
        }
    
        /** * 逆序寻找 */
        public int lastIndexOf(Object o) { 
            ListIterator<E> it = listIterator(size());
            if (o == null) { 
                while (it.hasPrevious())
                    if (it.previous() == null)
                        return it.nextIndex();
            } else { 
                while (it.hasPrevious())
                    if (o.equals(it.previous()))
                        return it.nextIndex();
            }
            return -1;
        }
    
    
        // Bulk Operations
    
        /** * 通过Iterator提供的remove功能，遍历时remove。 */
        public void clear() { 
            removeRange(0, size());
        }
    
        /** * 遍历调用add()方法 */
        public boolean addAll(int index, Collection<? extends E> c) { 
            rangeCheckForAdd(index);
            boolean modified = false;
            for (E e : c) { 
                add(index++, e);
                modified = true;
            }
            return modified;
        }
    
    
        // Iterators
    
        /** * 以适当的顺序返回此列表中元素的迭代器。 */
        public Iterator<E> iterator() { 
            return new Itr();
        }
    
        /** * 以适当的顺序返回此列表中元素的List迭代器。 */
        public ListIterator<E> listIterator() { 
            return listIterator(0);
        }
    
        /** * 以适当的顺序返回此列表中从index开始的元素的List迭代器。 */
        public ListIterator<E> listIterator(final int index) { 
            rangeCheckForAdd(index);
    
            return new ListItr(index);
        }
         /** * 一个实现了 Iterator 接口的内部迭代器 */
        private class Itr implements Iterator<E> { 
            // 为了版面，此处省去
        }
    
        /** * 为了listIterator()方法，所以再写实现一个ListIterator */
        private class ListItr extends Itr implements ListIterator<E> { 
            // 为了版面，此处省去
        }
    
        /** * 如果实现类已经写了 */
        public List<E> subList(int fromIndex, int toIndex) { 
            return (this instanceof RandomAccess ?
                    new RandomAccessSubList<>(this, fromIndex, toIndex) :
                    new SubList<>(this, fromIndex, toIndex));
        }
    
        // Comparison and hashing
    
        /** * 还是通过迭代器遍历，必须两者顺序元素都相同. */
        public boolean equals(Object o) { 
            if (o == this)
                return true;
            if (!(o instanceof List))
                return false;
    
            ListIterator<E> e1 = listIterator();
            ListIterator<?> e2 = ((List<?>) o).listIterator();
            while (e1.hasNext() && e2.hasNext()) { 
                E o1 = e1.next();
                Object o2 = e2.next();
                if (!(o1 == null ? o2 == null : o1.equals(o2)))
                    return false;
            }
            return !(e1.hasNext() || e2.hasNext());
        }
    
        /** * 遍历List中的每个元素，求出Hash值进行累加. */
        public int hashCode() { 
            int hashCode = 1;
            for (E e : this)
                hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
            return hashCode;
        }
    
        /** * 删除[fromIndex,toIndex)中的所有值 * * @param fromIndex 第一个被移除的元素的下标 * @param toIndex 最后一个被移除的元素的后一个下标 */
        protected void removeRange(int fromIndex, int toIndex) { 
            ListIterator<E> it = listIterator(fromIndex);
            for (int i = 0, n = toIndex - fromIndex; i < n; i++) { 
                it.next();
                it.remove();
            }
        }
    
        protected transient int modCount = 0;
    
        private void rangeCheckForAdd(int index) { 
            if (index < 0 || index > size())
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    
        private String outOfBoundsMsg(int index) { 
            return "Index: " + index + ", Size: " + size();
        }
    }
    
    /** * 此处这个subList是解决subList(int,int)方法的类 */
    class SubList<E> extends AbstractList<E> { 
        // 为了版面，此处省去
    }
    
    /** * 实现类如果支持随机读写,那么使用RandomAccessSubList更合适. */
    class RandomAccessSubList<E> extends SubList<E> implements RandomAccess { 
        // 为了版面，此处省去
    }

所以如果我们自己想要实现List接口，那么先继承AbstractList类，往往能让类中的方法数量大大减少，毕竟大多数情况我们只是想增删改查，多余的方法可以忽视.

# ArrayList源码解析 #

在Java中提供了两个非常常用的数据结构-------ArrayList和LinkedList，ArrayList本质上就是一个可扩容数组，LinkedList本质上就是一个双向链表.

两者对外的接口都是List接口，所以其拥有的功能几乎相同，但是内部实现完全是两套体系，如果不知道这两者的区别，那么很难说出对应的优点和缺点。

## ArrayList的知识 ##

ArrayList通过数组实现一个List，其本质上是对一个数组的简单封装，所以最后表现出来的特点是一个可扩容数组。

在大多数情况下，我们只需要直到ArrayList底层是一个可扩容数组就可以了，但是在面试中ArrayList这一内容被问的五花八门，我在这里统一进行一次解析。

**从UML 出发**

!\[1559201746116\](C:\\Users\\10146\\Pictures\\技术\\数据结构\\2. 线性表\\ArrayList\\ArrayList的UML图.png)![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70]

上图右边的三个接口（RandomAccess, Cloneable, java.io.Serializable）就是标识接口，只起一个标识作用，代表ArrayList实现了这三个接口，并没有实际上的约束,只是大家约定俗成。

> 在接下来的源码分析中，与这三个接口相关的方法和变量我会有意删减。

而其左侧继承了AbstractList，这意味着ArrayList并不需要实现List接口中的每一个内容，而只是从中选出一部分方法进行实现。

## ArrayList的内部结构 ##

ArrayList见名知意，内部实现是通过数组(Array)实现。对于一个数组来说，其大小在申请后就不可以再改变了。所以ArrayList首要解决的问题就是数组的大小问题，数组过大，浪费内存严重，数组过小，又无法改变其大小。

当然ArrayList的设计者自然找到了一种平衡，过大的危害太严重，而过小的危害似乎可以避免，因为如果是内部数组，那么内部只保留了一个数组的引用，虽然数组的大小在申请后就不可改变了，但是引用可以从本来指向一个较小的数组变为指向一个较大的数组。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 1]

数组的长度绝对不能小于元素的个数，所以size()方法返回的应该是元素的个数，而不是数组的长度.那么我就可以很轻易的写出一个特别轻量级的ArrayList。

import java.util.AbstractList;
    import java.util.List;
    
    /** * ArrayList实现了四个接口（标识接口已被我删去），继承了一个抽象类 */
    public class ArrayList<E> extends AbstractList<E>
            implements List<E> { 
        /** * 存储元素的数组 */
        transient Object[] elementData; // non-private to simplify nested class access
    
        /** * ArrayList的大小（它包含的元素数）。 */
        private int size;
    
        // init Operation
        public ArrayList() { 
            // 默认给其一个空数组,其size默认值为 0.
            this.elementData = new Object[]{ };
        }
    
        /** * get方法 * * @param index 下标 * @return 返回元素 */
        @Override
        public E get(int index) { 
            return (E) elementData[index];
        }
    
        /** * 返回List中元素的个数 * * @return 返回List中的个数 */
        @Override
        public int size() { 
            return size;
        }
    }

虽然这个ArrayList没啥用，但是java.util.ArrayList的基本的框架就是这个样子.

我们现在的问题有很多：

1.  现在这个数组是空的，无法放入元素。
2.  内部数组的扩容操作要在哪里实现，是增加前扩容，还是增加后扩容？ 在删除元素后数组大小还要缩小？
3.  增删改功能一个都没实现，现在的代码完全是一个花架子。
4.  对于ArrayList来说，List接口中那些是不必要的呢？那些是必要的?

### ArrayList的初始化 ###

很明显前一个ArrayList的初始化不太让人满意，我在这里直接把底层的所有构造方法放在这里，并讲解其作用.

/** * 空数组 */
        private static final Object[] EMPTY_ELEMENTDATA = { };
        /** * 默认数组(刚开始为0，在添加第一个元素时变为len = 10),防止空ArrayList占用内存过多. */
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };
    
        //init Operation
    
        /** * 用户传入一个大小，申请对应大小的数组, * (PS:如果不这样做，在很多数据量很大，而且时间比较敏感的情况下，会浪费大量时间进行扩容操作) * * @param initialCapacity 传入初始化容量 */
        public ArrayList(int initialCapacity) { 
            if (initialCapacity > 0) { 
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) { 
                this.elementData = EMPTY_ELEMENTDATA;
            } else { 
                // 抛出异常，初始化容量 < 0
                throw new IllegalArgumentException("Illegal Capacity: " +
                        initialCapacity);
            }
        }
    
        /** * 虽然DEFAULTCAPACITY_EMPTY_ELEMENTDATA是空的数组，但是在稍后添加第一个元素时，会将其容量改为10. */
        public ArrayList() { 
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    
        /** * 按照集合的iterator返回的顺序构造一个包含指定Collction元素的List。 * * @param c 待添加元素的集合 */
        public ArrayList(Collection<? extends E> c) { 
            elementData = c.toArray();
            if ((size = elementData.length) != 0) { 
                // c.toArray might (incorrectly) not return Object[] (see 6260652)
                if (elementData.getClass() != Object[].class)
                    elementData = Arrays.copyOf(elementData, size, Object[].class);
            } else { 
                // replace with empty array.
                this.elementData = EMPTY_ELEMENTDATA;
            }
        }

### ArrayList的改操作 ###

/** * 修改index值为element * * @param index * @param element * @return */
        public E set(int index, E element) { 
    
            E oldValue = (E) elementData[index];
            elementData[index] = element;
            return oldValue;
        }

修改就是很简单的三句话,这是增删改查中最简单的功能了.

### ArrayList的查询元素 ###

可能你认为一个get(int)就可以解决所有查的可能性，但是事实上是再实际开发中，我们往往除了使用index查询元素意外，往往还想通过元素找到对应的第一个下标，最后一个下标。

// query
        /** * 找到o在List出现的第一次下标，找不到就返回 -1 * * @param o 寻找元素 * @return 对应下标idx */
        public int indexOf(Object o) { 
            if (o == null) { 
                for (int i = 0; i < size; i++)
                    if (elementData[i] == null)
                        return i;
            } else { 
                for (int i = 0; i < size; i++)
                    if (o.equals(elementData[i]))
                        return i;
            }
            return -1;
        }
    
        /** * 找到o在List出现的最后一次下标，找不到就返回 -1 * * @param o 寻找元素 * @return 对应下标idx */
        public int lastIndexOf(Object o) { 
            if (o == null) { 
                for (int i = size - 1; i >= 0; i--)
                    if (elementData[i] == null)
                        return i;
            } else { 
                for (int i = size - 1; i >= 0; i--)
                    if (o.equals(elementData[i]))
                        return i;
            }
            return -1;
        }
    
        /** * get方法 * * @param index 下标 * @return 返回元素 */
        @Override
        public E get(int index) { 
            return (E) elementData[index];
        }

### ArrayList 删除元素 ###

删除的话，覆盖的是remove(int) 和remove(Object)方法

/** * 将index对应得元素删除，其之后所有元素向前一步走。 * * @param index 对应下标 * @return 删除得元素值 */
        E remove(int index);
    
        /** * 从此List中删除第一次出现的指定元素 * * @param o 待删除元素 * @return 删除成功则<tt>true</tt> */
        @Override
        boolean remove(Object o);
    
        /** * 从此列表中删除指定集合中包含的所有元素（可选。 * * @param c 待删除元素的集合 * @return <tt>true</tt> */
        boolean removeAll(Collection<?> c);
    
        /** * 从此列表中删除所有元素（可选操作）。 * 此调用返回后列表将为空。 */
        void clear();

ArrayList是如何实现的呢？

/** * 移除index位置的元素，并且之后的元素向前补位 * * @throws IndexOutOfBoundsException {@inheritDoc} */
        public E remove(int index) { 
            // 检查边界，防止越界
    
            E oldValue = (E) elementData[index];
            fastRemove(index);
            return oldValue;
        }
    
        /** * 删除第一次出现的元素 o */
        public boolean remove(Object o) { 
            if (o == null) { 
                for (int index = 0; index < size; index++) { 
                    if (elementData[index] == null) { 
                        fastRemove(index);
                        return true;
                    }
                }
            } else { 
                for (int index = 0; index < size; index++) { 
                    if (o.equals(elementData[index])) { 
                        fastRemove(index);
                        return true;
                    }
                }
            }
            return false;
        }
    
        /** * 将index之后的所有元素都向前一步走.之后原来的最后一个元素置为null,且size--即可 */
        private void fastRemove(int 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
        }
    
        /** * 将数组的中所有元素置为null，销毁数据。 */
        public void clear() { 
    
            // clear to let GC do its work
            for (int i = 0; i < size; i++)
                elementData[i] = null;
    
            size = 0;
        }
    
        /** * 求交集，只保留交集中的重复元素. * * @param c 集合 * @return */
        public boolean removeAll(Collection<?> c) { 
            Objects.requireNonNull(c);
            return batchRemove(c, false);
        }
    
        /** * 批量删除 * @param c * @param complement * @return */
        private boolean batchRemove(Collection<?> c, boolean complement) { 
            final Object[] elementData = this.elementData;
            int r = 0, w = 0;
            boolean modified = false;
            try { 
                for (; r < size; r++)
                    if (c.contains(elementData[r]) == complement)
                        elementData[w++] = elementData[r];
            } finally { 
                // Preserve behavioral compatibility with AbstractCollection,
                // even if c.contains() throws.
                if (r != size) { 
                    System.arraycopy(elementData, r,
                            elementData, w,
                            size - r);
                    w += size - r;
                }
                if (w != size) { 
                    // clear to let GC do its work
                    for (int i = w; i < size; i++)
                        elementData[i] = null;
                    size = w;
                    modified = true;
                }
            }
            return modified;
        }

### ArrayList的增加 ###

对ArrayList的操作中，增加元素将会是最为繁琐的步骤，因为需要考虑的情况很多：

*  如果数组已满，什么时候扩容？
 *  一个数值插入到对应idx处，后面的元素怎么最快的后移
 *  扩容的话，容量增加多少为合适？
 *  当第一次添加元素时，数组从默认的空数组变为多大的数组？
 *  如何将另一个实现了Collection接口的容器中的数据都加入到List中？甚至插入到idx处去？

在初始化时，如果用户没有传入初始大小参数，那么默认数组容量为0，但是当添加第一个元素的时候，其容量变为10.

/** * 在List尾部进行新增. */
        public boolean add(E e) { 
            // 新增元素，需要先判断数组的容量是否足够使用，如果不够则对数组引用进行扩容
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }
    
        /** * 在index位置插入，原来>=index的元素都向后移动一位. size++; */
        public void add(int index, E element) { 
            // 确保容量
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            System.arraycopy(elementData, index, elementData, index + 1,
                    size - index);
            elementData[index] = element;
            size++;
        }
    
        /** * 确保数组的容量（如果是size==0的初始数组(不是empty_Data)，那么容量为10） */
        private void ensureCapacityInternal(int minCapacity) { 
            // 如果是初始空数组，那么申请一个 size = 10的数组(也就是默认容量)
            int capacity = calculateCapacity(elementData, minCapacity);
    		
            ensureExplicitCapacity(capacity);
        }
    
        /** * 确保数组的最小容量 */
        public void ensureCapacity(int minCapacity) { 
            int minExpand =
                    (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
    
            if (minCapacity > minExpand) { 
                ensureExplicitCapacity(minCapacity);
            }
        }
    
        /** * 明确的确保数组容量 */
        private void ensureExplicitCapacity(int minCapacity) { 
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
    
        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
        // grow，一般为1.5倍扩容，只有当1.5倍后的结果超过最大范围时，才会用到传入的minCapacity
        private void grow(int minCapacity) { 
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity通常接近大小，所以这也是一个成功的扩容
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    
        private static int hugeCapacity(int minCapacity) { 
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError
                        ("Required array size too large");
            return (minCapacity > MAX_ARRAY_SIZE) ?
                    Integer.MAX_VALUE :
                    MAX_ARRAY_SIZE;
        }
    
        private static final int DEFAULT_CAPACITY = 10;
    
        /** * 如果是默认数组，且用户传入size小于10，则改为10 * * @param elementData 元素数组 */
        private static int calculateCapacity(Object[] elementData, int minCapacity) { 
            // DEFAULT_CAPACITY = 10;
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            return minCapacity;
        }
    
        /** * 将c的元素全部添加到List,从尾端插入. * * @return 是否成功 */
        public boolean addAll(Collection<? extends E> c) { 
            Object[] a = c.toArray();
            int numNew = a.length;
            ensureCapacityInternal(size + numNew);  // Increments modCount
            System.arraycopy(a, 0, elementData, size, numNew);
            size += numNew;
            return numNew != 0;
        }
    
        /** * 将c中的元素，加入到List中，从index位置开始插入. */
        public boolean addAll(int index, Collection<? extends E> c) { 
    
            Object[] a = c.toArray();
            int numNew = a.length;
            ensureCapacityInternal(size + numNew);  // Increments modCount
    
            int numMoved = size - index;
            if (numMoved > 0)
                System.arraycopy(elementData, index, elementData, index + numNew,
                        numMoved);
    
            System.arraycopy(a, 0, elementData, index, numNew);
            size += numNew;
            return numNew != 0;
        }

### ArrayList实现Collection中的一些必要方法 ###

package unit2;
    
    import java.util.*;
    /** * Collection类，其中一些1.8新特性已经删去 * ArrayList已经实现的功能也删去了. */
    public interface Collection<E> extends Iterable<E> { 
        // Query Operations
    
        boolean isEmpty();
    
        boolean contains(Object o);
    
        Iterator<E> iterator();
    
        Object[] toArray();
    
        <T> T[] toArray(T[] a);
    
        // Bulk Operations
    
        boolean retainAll(java.util.Collection<?> c);
    
        // Comparison and hashing
    	
        boolean equals(Object o);
    
        int hashCode();
        // jdk1.8 新特性此处不表
        // spliterator()
        // stream()
        // parallelStream()
        // removeIf(Predicate<? super E> filter)
    }

这些都由AbstractList的父类AbstractCollection实现过了,比如

public boolean isEmpty() { 
            return size() == 0;
        }
    	
    	public boolean contains(Object o) { 
            Iterator<E> it = iterator();
            if (o==null) { 
                while (it.hasNext())
                    if (it.next()==null)
                        return true;
            } else { 
                while (it.hasNext())
                    if (o.equals(it.next()))
                        return true;
            }
            return false;
        }
    
    	public Object[] toArray() { 
            // Estimate size of array; be prepared to see more or fewer elements
            Object[] r = new Object[size()];
            Iterator<E> it = iterator();
            for (int i = 0; i < r.length; i++) { 
                if (! it.hasNext()) // fewer elements than expected
                    return Arrays.copyOf(r, i);
                r[i] = it.next();
            }
            return it.hasNext() ? finishToArray(r, it) : r;
        }
    	// 为了版面，其他不写.

但是ArrayList是一个Java类库，而不是我们自己写的超轻量级List，所以再ArrayList中也实现了一遍Collection接口，为了更高的时间效率。

// collection
    
        public boolean isEmpty() { 
            return size == 0;
        }
    
        public boolean contains(Object o) { 
            return indexOf(o) >= 0;
        }
    
        /** * 将数组拷贝一份并返回 */
        public Object[] toArray() { 
            return Arrays.copyOf(elementData, size);
        }
    
        /** * 如果a的容量足够，则使用a，容量不足则仍使用toArray()方法 */
        public <T> T[] toArray(T[] a) { 
            if (a.length < size)
                // Make a new array of a's runtime type, but my contents:
                return (T[]) Arrays.copyOf(elementData, size, a.getClass());
            System.arraycopy(elementData, 0, a, 0, size);
            if (a.length > size)
                a[size] = null;
            return a;
        }
    
        /** * 调用批量删除,删除重复元素即可. */
        public boolean retainAll(Collection<?> c) { 
            Objects.requireNonNull(c);
            return batchRemove(c, true);
        }
    
        /** * 此处属于ArrayList的特殊操作，对容量进行一次修剪，使arr.len = size。避免浪费，到那时一般不使用这个方法。 * 只有当用户觉得size已经稳定时，才使用这个方法将数组容量修改为size。 */
        public void trimToSize() { 
            if (size < elementData.length) { 
                elementData = (size == 0)
                        ? EMPTY_ELEMENTDATA
                        : Arrays.copyOf(elementData, size);
            }
        }
    
        // 已经由AbstractList代劳.
        // boolean equals(Object o);
        //
        // int hashCode();

还有少数方法需要及其繁琐的实现，此处不写，其大多也并无太难理解的地方.

## ArrayList全部代码 ##

我在很多地方都写过一句：“检验边界，放置越界”，还有强制类型转化导致报warning错误，此处我在这里通过封装两个方法解决。

// 越界检测
    	private void rangeCheck(int index) { 
            if (index >= size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    
        private void rangeCheckForAdd(int index) { 
            if (index > size || index < 0)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    
        private String outOfBoundsMsg(int index) { 
            return "Index: "+index+", Size: "+size;
        }

强制类型转换放入方法中，其头部加上@SuppressWarnings(“unchecked”)注解解决warning.

@SuppressWarnings("unchecked")
        E elementData(int index) { 
            return (E) elementData[index];
        }

import java.util.*;
    import java.util.AbstractList;
    import java.util.List;
    /** * 实现了ArrayList大多数功能，其余功能可能是因为涉及到lambda表达式或者其他新特性， * 或者就是较为繁琐，而且读后可能收获并不太大。 */
    public class ArrayList<E> extends AbstractList<E>
            implements List<E> { 
        /** * 存储元素的数组 */
        private transient Object[] elementData; // non-private to simplify nested class access
    
    
        /** * ArrayList的大小（它包含的元素数）。 */
        private int size;
    
        /** * 空数组 */
        private static final Object[] EMPTY_ELEMENTDATA = { };
    
        /** * 默认数组(刚开始为0，在添加第一个元素时变为len = 10),防止空ArrayList占用内存过多. */
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };
    
        //init Operation
    
        /** * 用户传入一个大小，申请对应大小的数组, * (PS:如果不这样做，在很多数据量很大，而且时间比较敏感的情况下，会浪费大量时间进行扩容操作) * * @param initialCapacity 传入初始化容量 */
        public ArrayList(int initialCapacity) { 
            if (initialCapacity > 0) { 
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) { 
                this.elementData = EMPTY_ELEMENTDATA;
            } else { 
                // 抛出异常，初始化容量 < 0
                throw new IllegalArgumentException("Illegal Capacity: " +
                        initialCapacity);
            }
        }
    
        /** * 虽然DEFAULTCAPACITY_EMPTY_ELEMENTDATA是空的数组，但是在稍后添加第一个元素时，会将其容量改为10. */
        public ArrayList() { 
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    
        /** * 按照集合的iterator返回的顺序构造一个包含指定Collction元素的List。 * * @param c 待添加元素的集合 */
        public ArrayList(Collection<? extends E> c) { 
            elementData = c.toArray();
            if ((size = elementData.length) != 0) { 
                // c.toArray might (incorrectly) not return Object[] (see 6260652)
                if (elementData.getClass() != Object[].class)
                    elementData = Arrays.copyOf(elementData, size, Object[].class);
            } else { 
                // replace with empty array.
                this.elementData = EMPTY_ELEMENTDATA;
            }
        }
    
    
        /** * size值的主要用处之一. * * @return 返回List中的个数 */
        @Override
        public int size() { 
            return size;
        }
    
        /** * 移除index位置的元素，并且之后的元素向前补位 */
        public E remove(int index) { 
            // 检查边界，防止越界
            rangeCheck(index);
            E oldValue = elementData(index);
            fastRemove(index);
            return oldValue;
        }
    
        /** * 删除第一次出现的元素 o */
        public boolean remove(Object o) { 
            if (o == null) { 
                for (int index = 0; index < size; index++) { 
                    if (elementData[index] == null) { 
                        fastRemove(index);
                        return true;
                    }
                }
            } else { 
                for (int index = 0; index < size; index++) { 
                    if (o.equals(elementData[index])) { 
                        fastRemove(index);
                        return true;
                    }
                }
            }
            return false;
        }
    
        /** * 将index之后的所有元素都向前一步走.之后原来的最后一个元素置为null,且size--即可 */
        private void fastRemove(int 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
        }
    
        /** * 将数组的中所有元素置为null，销毁数据。 */
        public void clear() { 
            // 置为null，等待GC回收
            for (int i = 0; i < size; i++)
                elementData[i] = null;
            size = 0;
        }
    
        /** * 求交集，只保留交集中的重复元素. * * @param c 集合 */
        public boolean removeAll(Collection<?> c) { 
            Objects.requireNonNull(c);
            return batchRemove(c, false);
        }
    
        /** * 批量删除 */
        private boolean batchRemove(Collection<?> c, boolean complement) { 
            final Object[] elementData = this.elementData;
            int r = 0, w = 0;
            boolean modified = false;
            try { 
                for (; r < size; r++)
                    if (c.contains(elementData[r]) == complement)
                        elementData[w++] = elementData[r];
            } finally { 
                // Preserve behavioral compatibility with AbstractCollection,
                // even if c.contains() throws.
                if (r != size) { 
                    System.arraycopy(elementData, r,
                            elementData, w,
                            size - r);
                    w += size - r;
                }
                if (w != size) { 
                    // clear to let GC do its work
                    for (int i = w; i < size; i++)
                        elementData[i] = null;
                    size = w;
                    modified = true;
                }
            }
            return modified;
        }
    
        // query
    
        /** * 找到o在List出现的第一次下标，找不到就返回 -1 * * @param o 寻找元素 * @return 对应下标idx */
        public int indexOf(Object o) { 
            if (o == null) { 
                for (int i = 0; i < size; i++)
                    if (elementData[i] == null)
                        return i;
            } else { 
                for (int i = 0; i < size; i++)
                    if (o.equals(elementData[i]))
                        return i;
            }
            return -1;
        }
    
        /** * 找到o在List出现的最后一次下标，找不到就返回 -1 * * @param o 寻找元素 * @return 对应下标idx */
        public int lastIndexOf(Object o) { 
            if (o == null) { 
                for (int i = size - 1; i >= 0; i--)
                    if (elementData[i] == null)
                        return i;
            } else { 
                for (int i = size - 1; i >= 0; i--)
                    if (o.equals(elementData[i]))
                        return i;
            }
            return -1;
        }
    
        /** * get方法 * * @param index 下标 * @return 返回元素 */
        @Override
        public E get(int index) { 
            rangeCheck(index);
            return elementData(index);
        }
    
        // update
    
        /** * 修改index值为element */
        public E set(int index, E element) { 
            rangeCheck(index);
            E oldValue = elementData(index);
            elementData[index] = element;
            return oldValue;
        }
    
        // add
    
        /** * 在List尾部进行新增. */
        public boolean add(E e) { 
            
            // 新增元素，需要先判断数组的容量是否足够使用，如果不够则对数组引用进行扩容
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }
    
        /** * 在index位置插入，原来>=index的元素都向后移动一位. size++; */
        public void add(int index, E element) { 
            rangeCheckForAdd(index);
            // 确保容量
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            System.arraycopy(elementData, index, elementData, index + 1,
                    size - index);
            elementData[index] = element;
            size++;
        }
    
        /** * 确保数组的容量（如果是size==0的初始数组(不是empty_Data)，那么容量为10） */
        private void ensureCapacityInternal(int minCapacity) { 
            // 如果是初始空数组，那么申请一个 size = 10的数组(也就是默认容量)
            int capacity = calculateCapacity(elementData, minCapacity);
    
            ensureExplicitCapacity(capacity);
        }
    
        public void ensureCapacity(int minCapacity) { 
            int minExpand =
                    (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
    
            if (minCapacity > minExpand) { 
                ensureExplicitCapacity(minCapacity);
            }
        }
    
        /** * 明确的确保容量 */
        private void ensureExplicitCapacity(int minCapacity) { 
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
    
        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
        // grow，一般为1.5倍扩容，只有当1.5倍后的结果超过最大范围时，才会用到传入的minCapacity
        private void grow(int minCapacity) { 
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity通常接近大小，所以这也是一个成功的扩容
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    
        private static int hugeCapacity(int minCapacity) { 
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError
                        ("Required array size too large");
            return (minCapacity > MAX_ARRAY_SIZE) ?
                    Integer.MAX_VALUE :
                    MAX_ARRAY_SIZE;
        }
    
        private static final int DEFAULT_CAPACITY = 10;
    
        /** * 如果是默认数组，且用户传入size小于10，则改为10 * * @param elementData 元素数组 * @param minCapacity 最小容量 * @return 数组合适的容量 */
        private static int calculateCapacity(Object[] elementData, int minCapacity) { 
            // DEFAULT_CAPACITY = 10;
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            return minCapacity;
        }
    
        /** * 将c的元素全部添加到List */
        public boolean addAll(Collection<? extends E> c) { 
            Object[] a = c.toArray();
            int numNew = a.length;
            ensureCapacityInternal(size + numNew);  // Increments modCount
            System.arraycopy(a, 0, elementData, size, numNew);
            size += numNew;
            return numNew != 0;
        }
    
        public boolean addAll(int index, Collection<? extends E> c) { 
    
            Object[] a = c.toArray();
            int numNew = a.length;
            ensureCapacityInternal(size + numNew);  // Increments modCount
    
            int numMoved = size - index;
            if (numMoved > 0)
                System.arraycopy(elementData, index, elementData, index + numNew,
                        numMoved);
    
            System.arraycopy(a, 0, elementData, index, numNew);
            size += numNew;
            return numNew != 0;
        }
    
        // collection
    
        public boolean isEmpty() { 
            return size == 0;
        }
    
        public boolean contains(Object o) { 
            return indexOf(o) >= 0;
        }
    
        /** * 将数组拷贝一份并返回 */
        public Object[] toArray() { 
            return Arrays.copyOf(elementData, size);
        }
    
        /** * 如果a的容量足够，则使用a，容量不足则仍使用toArray()方法 */
        @SuppressWarnings("unchecked")
        public <T> T[] toArray(T[] a) { 
            if (a.length < size)
                // Make a new array of a's runtime type, but my contents:
                return (T[]) Arrays.copyOf(elementData, size, a.getClass());
            System.arraycopy(elementData, 0, a, 0, size);
            if (a.length > size)
                a[size] = null;
            return a;
        }
    
        /** * 调用批量删除,删除重复元素即可. */
        public boolean retainAll(Collection<?> c) { 
            Objects.requireNonNull(c);
            return batchRemove(c, true);
        }
    
        /** * 当用户觉得size已经稳定时，使用这个方法将数组容量修改为size。 */
        public void trimToSize() { 
            if (size < elementData.length) { 
                elementData = (size == 0)
                        ? EMPTY_ELEMENTDATA
                        : Arrays.copyOf(elementData, size);
            }
        }
    
        // 已经由AbstractList代劳.
        // boolean equals(Object o);
        //
        // int hashCode();
    
        // 越界检测
        private void rangeCheck(int index) { 
            if (index >= size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    
        private void rangeCheckForAdd(int index) { 
            if (index > size || index < 0)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    
        private String outOfBoundsMsg(int index) { 
            return "Index: "+index+", Size: "+size;
        }
        @SuppressWarnings("unchecked")
        private  E elementData(int index) { 
            return (E) elementData[index];
        }
    }

## ArrayList总结 ##

ArrayList内部封装了一个数组引用，使得其可以伪装为数组动态扩容，但是实际上数组的容量在申请后就不可以增加或者缩小了，其中动态扩容是著名的考题。比如：

> 数组怎样实现扩容？

封装数组扩容，

> ArrayList一般扩容为原本的多少倍？

1.5倍扩容，

> 为什么建议给ArrayList一个初始容量？

(扩容本质上就是申请内存，比较吃时间，给定容量可以大幅减少扩容次数，从而优化时间。)

> ArrayList与Vector的区别在哪里？

ArrayList会鸽Vector都是基于数组的线性表，很多代码都是重复的，但是Vector是一个线程安全的线性表，其内部存在大量的“**synchronized**”锁，并且Vector扩容方式为2倍扩容，而ArrayList线程不安全，1.5倍扩容，我们一般情况下不推荐使用Vector,

> ArrayList默认容量10

在添加第一个元素之前，默认容量为0，节省空间，在添加第一个元素是，其默认容量为10.

> ArrayList和LinkedList的区别?

ArrayList和LinkedList的区别本质上就是数组与链表的区别，数组能够随机读取，但是增加或三处速度较慢，而且扩容比较吃时间，链表则与其相反。

> LinkedList的本质？

含有指向头尾节点的双向链表(非循环).

> ArrayList 和int\[\] 的区别?

ArrayList只能容纳对象，无法容纳基本类型，所以在加入时比较耗费时间，因为要进行自动装箱。我们在时间不敏感时，或者比较小型的集合时，推荐使用ArrayList，此时程序员的效率重要性大于执行效率.

[ArrayList_LinkedList]: https://blog.csdn.net/m0_37961948/article/details/81805737
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70]: /images/20220125/ee9a6a44c39a4605ae29e6228b68ba50.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 1]: /images/20220125/3872eda6730a4d6b92a55cb3faccb8b3.png