JDK集合源码之ArrayList解析(附带面试题举例)-阿里云开发者社区

声明：尊重他人劳动成果，转载请附带原文链接！

1. ArrayList 继承体系

ArrayList 又称动态数组，底层是基于数组实现的List，与数组的区别在于，其具备动态扩展能力。从继承体系图中可看出ArrayList：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
  ...
}

实现了List, RandomAccess， Cloneable， java.io.Serializable等接口

实现了List，具备基础的添加、删除、遍历等操作

实现了RandomAccess，具备随机访问的能力

实现了Cloneable，可以被克隆(浅拷贝) list.clone()

实现了Serializable，可以被序列化

2. ArrayList 实现Cloneable，RandomAccess，Serializable接口

实现Cloneable接口，可以被浅拷贝

 /**
  * Returns a shallow copy of this <tt>ArrayList</tt> instance.  (The
  * elements themselves are not copied.)
  * 返回此<tt> ArrayList </ tt>实例的拷贝副本。 （元素本身不会被复制。）
  *
  * @return a clone of this <tt>ArrayList</tt> instance
  */
 public Object clone() {
     try {
         ArrayList<?> v = (ArrayList<?>) super.clone();
         // 拷贝
         v.elementData = Arrays.copyOf(elementData, size);
         v.modCount = 0;
         return v;
     } catch (CloneNotSupportedException e) {
         // this shouldn't happen, since we are Cloneable
         throw new InternalError(e);
     }
 }

在java语言中，对象实现 Cloneable 接口时，能够对其进行深拷贝和浅拷贝，这里简述下，深拷贝和浅拷贝的区别：

首先创建一个User类：

/**
 * @Auther: csp1999
 * @Date: 2020/10/28/15:51
 * @Description:
 */
public class User {
    private String name;// user名称
    public String getName() {return name;}
    public void setName(String name) {this.name = name; }
    public User(String name) { this.name = name;}
    public User() {}
    @Override
    public String toString() {
        return "User{" +
                "name='" + name + '\'' +
                '}';
    }
}

下面来看浅拷贝实例：

@Test
public void test02() {
    /**
     * 简单演示ArrayList 浅拷贝:
     */
    ArrayList list = new ArrayList();
    //User 对象实例化
    User user = new User("csp");
    list.add("abc");// list添加简单字符类型
    list.add(user);// list添加对象类型
    System.out.println("------------原始ArrayList集合------------");
    System.out.println("list:"+list);
    // 浅拷贝
  ArrayList clone = (ArrayList) list.clone();
  System.out.println("------------浅拷贝后得到的新ArrayList集合------------");
  System.out.println("二者地址是否相同：" + (list == clone));
  System.out.println("------------未修改list中的User属性之前------------");
  System.out.println("clone:"+clone);
  System.out.println("------------当修改list中的User属性之后------------");
  User u = (User) list.get(1);
  u.setName("csp1999");
  System.out.println("clone:"+clone);
  System.out.println("clone中的user对象和原始list中的user对象地址是否相同："+(list.get(1)==clone.get(1)));
}

输出结果：

------------原始ArrayList集合------------
list:[abc, User{name='csp'}]
------------浅拷贝后得到的新ArrayList集合------------
二者地址是否相同：false
------------未修改list中的User属性之前------------
clone:[abc, User{name='csp'}]
------------当修改list中的User属性之后------------
clone:[abc, User{name='csp1999'}]
clone中的user对象和原始list中的user对象地址是否相同：true

由结果可得出结论：

当最初的list 集合被克隆之后，实际上是产生了一个新的ArrayList对象，二者地址引用不相同

当从list集合中获取到user对象并修改其属性之后，clone集合中的user属性也对应发生了改变，这就说明，clone在复制list集合时，对复杂的对象类型数据元素，只是拷贝了其地址引用，并未对其进行新建对象

因此，执行list.get(1)==clone.get(1))代码的时候，二者存储的user是同一个user对象，地址和数据均相同

而如果进行深拷贝时，就会在list被克隆新创建克隆对象时，对其存储的复杂对象类型也进行对象新创建，复杂对象类型数据获得新的地址引用，而不是像浅拷贝那样，仅仅拷贝了复杂对象类型的地址引用。

实现RandomAccess接口，可以提高随机访问列表的效率

ArrayList 实现了RandomAccess接口，因此当执行随机访问列表的时候，效率要高于顺序访问列表的效率，我们来看一个例子：

@Test
public void test03() {
    ArrayList arrayList = new ArrayList();
    for (int i=0;i<=99999;i++){// 集合中添加十万条数据
        arrayList.add(i);
    }
    // 测试随机访问的效率：
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < arrayList.size(); i++) {// 随机访问
        // 从集合中访问每一个元素
        arrayList.get(i);
    }
    long endTime = System.currentTimeMillis();
    System.out.println("执行随机访问所用时间："+(endTime-startTime));
    // 测试顺序访问的效率：
    startTime = System.currentTimeMillis();
    Iterator it = arrayList.iterator();// 顺序访问，也可以使用增强for
    while (it.hasNext()){
        // 从集合中访问每一个元素
        it.next();
    }
    endTime = System.currentTimeMillis();
    System.out.println("执行顺序访问所用时间："+(endTime-startTime));
}

查看输出结果：

执行随机访问所用时间：1
执行顺序访问所用时间：3

可以看出实现RandomAccess接口的ArrayList 进行随机访问的效率高于进行顺序访问的效率。

作为对比我们再来看一下未实现RandomAccess接口的LinkedList集合，测试随机访问和顺序访问列表的效率对比：

@Test
public void test04() {
    LinkedList linkedList = new LinkedList();
    for (int i=0;i<=99999;i++){// 集合中添加十万条数据
        linkedList.add(i);
    }
    // 测试随机访问的效率：
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < linkedList.size(); i++) {// 随机访问
        // 从集合中访问每一个元素
        linkedList.get(i);
    }
    long endTime = System.currentTimeMillis();
    System.out.println("执行随机访问所用时间："+(endTime-startTime));
    // 测试顺序访问的效率：
    startTime = System.currentTimeMillis();
    Iterator it = linkedList.iterator();// 顺序访问，也可以使用增强for
    while (it.hasNext()){
        // 从集合中访问每一个元素
        it.next();
    }
    endTime = System.currentTimeMillis();
    System.out.println("执行顺序访问所用时间："+(endTime-startTime));
}

查看输出结果：

执行随机访问所用时间：4601
执行顺序访问所用时间：2

由结果可得出结论，没有实现RandomAccess接口的LinkedList集合，测试随机访问的效率远远低于顺序访问。

3. ArrayList 属性

/**
 * Default initial capacity.
 * 默认容量
 */
private static final int DEFAULT_CAPACITY = 10;
/**
 * Shared empty array instance used for empty instances.
 * 空数组，如果传入的容量为0时使用
 */
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
 * 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.
 * 默认空容量的数组，长度为0，传入容量时使用，添加第一个元素的时候会重新初始为默认容量大小
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_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
/**
 * The size of the ArrayList (the number of elements it contains).
 * 集合中元素的个数
 * @serial
 */
private int size;

DEFAULT_CAPACITY：集合的默认容量，默认为10，通过new ArrayList()创建List集合实例时的默认容量是10。

EMPTY_ELEMENTDATA：空数组，通过new ArrayList(0)创建List集合实例时用的是这个空数组。

DEFAULTCAPACITY_EMPTY_ELEMENTDATA：默认容量空数组，这种是通过new ArrayList()无参构造方法创建集合时用的是这个空数组，与EMPTY_ELEMENTDATA的区别是在添加第一个元素时使用这个空数组的会初始化为DEFAULT_CAPACITY(10)个元素。

elementData：存储数据元素的数组，使用transient修饰，该字段不被序列化。

size：存储数据元素的个数，elementData数组的长度并不是存储数据元素的个数。

4. ArrayList 构造方法

ArrayList(int initialCapacity)有参构造方法

/**
 * 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
 *
 * 传入初始容量，如果大于0就初始化elementData为对应大小，如果等于0就使用EMPTY_ELEMENTDATA空数组，
 * 如果小于0抛出异常。
 */
// ArrayList(int initialCapacity)构造方法
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("不合理的初识容量: " +
                initialCapacity);
    }
}

ArrayList()空参构造方法

 /**
  * Constructs an empty list with an initial capacity of ten.
  * 构造一个初始容量为10的空数组
  *
  * 不传初始容量，初始化为DEFAULTCAPACITY_EMPTY_ELEMENTDATA空数组，
  * 会在添加第一个元素的时候扩容为默认的大小，即10。
  */
 public ArrayList() {
     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
 }

ArrayList(Collection c)有参构造方法

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 * 把传入集合的元素初始化到ArrayList中
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public ArrayList(Collection<? extends E> c) {
    // 将构造方法中的集合参数转换成数组
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // 检查c.toArray()返回的是不是Object[]类型，如果不是，重新拷贝成Object[].class类型
        if (elementData.getClass() != Object[].class)
          // 数组的创建与拷贝
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 如果c是空的集合，则初始化为空数组EMPTY_ELEMENTDATA
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

问题：为什么要检查检查c.toArray()返回的是不是Object[]类型，重新拷贝成Object[].class类型呢？

首先，我们都知道Object 是java中的超级父类，所有类都间接或者直接继承于Object，接着我们来看一个例子：

/**
 * @Auther: csp1999
 * @Date: 2020/10/27/23:22
 * @Description:
 */
public class ArrayListTest {
    class Father {}
    class Son extends Father {}
    class MyList extends ArrayList<String> {
        /**
         * 子类重写父类的方法,返回值可以不一样,但这里只能用数组类型，
         * 换成Object就不行,应该算是java本身的bug
         */
        @Override
        public String[] toArray() {
            // 为了方便举例直接写死
            return new String[]{"a", "b", "c"};
        }
    }
    @Test
    public void test01() {
        Father[] fathers = new Son[]{};
        // 打印结果为: class [Lcom.haust.test.ArrayListTest$Son;
        System.out.println(fathers.getClass());
        List<String> strList = new MyList();
        // 打印结果为: class [Ljava.lang.String;
        System.out.println(strList.toArray().getClass());
    }
}

5. ArrayList 相关操作方法

add(E e)添加元素到集合中

添加元素到末尾，平均时间复杂度为O(1)：

 /**
 * Appends the specified element to the end of this list.
 * 添加元素到末尾，平均时间复杂度为O(1)
 *  * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
  */
 public boolean add(E e) {
     // 每加入一个元素，minCapacity大小+1，并检查是否需要扩容
     ensureCapacityInternal(size + 1);  // Increments modCount!!
     // 把元素插入到最后一位
     elementData[size++] = e;
     return true;
 }
// 计算最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果是空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 返回DEFAULT_CAPACITY 和 minCapacity的大一方
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
// 检查是否需要扩容
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;// 数组结构被修改的次数+1
    // overflow-conscious code 储存元素的数据长度小于需要的最小容量时
    if (minCapacity - elementData.length > 0)
        // 扩容
        grow(minCapacity);
}
/**
 * 扩容
 * Increases the capacity to ensure that it can hold at lea
 * number of elements specified by the minimum capacity arg
 * 增加容量以确保它至少可以容纳最小容量参数指定的元素数量
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // 原来的容量
    int oldCapacity = elementData.length;
    // 新容量为旧容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果新容量发现比需要的容量还小，则以需要的容量为准
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果新容量已经超过最大容量了，则使用最大容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 以新容量拷贝出来一个新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}
// 使用最大容量
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
}

执行流程：

检查是否需要扩容；

如果elementData等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA则初始化容量大小为DEFAULT_CAPACITY；

新容量是老容量的1.5倍（oldCapacity + (oldCapacity >> 1)），如果加了这么多容量发现比需要的容量还小，则以需要的容量为准；

创建新容量的数组并把老数组拷贝到新数组；

add(int index, E element)添加元素到指定位置

添加元素到指定位置，平均时间复杂度为O(n)：

/**
 * 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).
 * 添加元素到指定位置，平均时间复杂度为O(n)。
 *  * @param index   指定元素要插入的索引
 * @param element 要插入的元素
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    // 检查是否越界
    rangeCheckForAdd(index);
    // 检查是否需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 将inex及其之后的元素往后挪一位，则index位置处就空出来了
    // **进行了size-索引index次操作**
    System.arraycopy(elementData, index, elementData, index + 1,
            size - index);
    // 将元素插入到index的位置
    elementData[index] = element;
    // 元素数量增1
    size++;
}
/**
 * A version of rangeCheck used by add and addAll.
 * add和addAll方法使用的rangeCheck版本
 */
// 检查是否越界
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

执行流程：

检查索引是否越界；
检查是否需要扩容；
把插入索引位置后的元素都往后挪一位；
在插入索引位置放置插入的元素；
元素数量增1；

addAll(Collection 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.)
 * 将集合c中所有元素添加到当前ArrayList中
 *  * @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) {
    // 将集合c转为数组
    Object[] a = c.toArray();
    int numNew = a.length;
    // 检查是否需要扩容
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 将c中元素全部拷贝到数组的最后
    System.arraycopy(a, 0, elementData, size, numNew);
    // 集合中元素的大小增加c的大小
    size += numNew;
    // 如果c不为空就返回true，否则返回false
    return numNew != 0;
}

执行流程：

拷贝c中的元素到数组a中；
检查是否需要扩容；
把数组a中的元素拷贝到elementData的尾部；

get(int index)获取指定索引位置的元素

获取指定索引位置的元素，时间复杂度为O(1)。

/**
 * Returns the element at the specified position in this list.
 *  * @param index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    // 检查是否越界
    rangeCheck(index);
    // 返回数组index位置的元素
    return elementData(index);
}
/**
 * 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];
}

执行流程：

检查索引是否越界，这里只检查是否越上界，如果越上界抛出IndexOutOfBoundsException异常，如果越下界抛出的是ArrayIndexOutOfBoundsException异常。

返回索引位置处的元素；

remove(int index)删除指定索引位置的元素

删除指定索引位置的元素，时间复杂度为O(n)。

/**
 * Removes the element at the specified position in this list.
 * Shifts any subsequent elements to the left (subtracts one from their
 * indices).
 * 删除指定索引位置的元素，时间复杂度为O(n)。
 *  * @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);
    // 集合底层数组结构修改次数+1
    modCount++;
    // 获取index位置的元素
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    // 如果index不是最后一位，则将index之后的元素往前挪一位
    if (numMoved > 0)
      // **进行了size-索引index-1次操作**
        System.arraycopy(elementData, index + 1, elementData, index,
                numMoved);
    // 将最后一个元素删除，帮助GC
    elementData[--size] = null; // clear to let GC do its work
    // 返回旧值
    return oldValue;
}

执行流程：

检查索引是否越界；

获取指定索引位置的元素；

如果删除的不是最后一位，则其它元素往前移一位；

将最后一位置为null，方便GC回收；

返回删除的元素。

注意：从源码中得出，ArrayList删除元素的时候并没有缩容。

remove(Object o)删除指定元素值的元素

删除指定元素值的元素，时间复杂度为O(n)。

/**
 * 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&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;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).
 * 删除指定元素值的元素，时间复杂度为O(n)。
 *  * @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) {
        // 遍历整个数组，找到元素第一次出现的位置，并将其快速删除
        for (int index = 0; index < size; index++)
            // 如果要删除的元素为null，则以null进行比较，使用==
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        // 遍历整个数组，找到元素第一次出现的位置，并将其快速删除
        for (int index = 0; index < size; index++)
            // 如果要删除的元素不为null，则进行比较，使用equals()方法
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}
/*
 * Private remove method that skips bounds checking and does not
 * return the value removed.
 * 专用的remove方法，跳过边界检查，并且不返回删除的值。
 */
private void fastRemove(int index) {
    // 少了一个越界的检查
    modCount++;
    // 如果index不是最后一位，则将index之后的元素往前挪一位
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index,
                numMoved);
    // 将最后一个元素删除，帮助GC
    elementData[--size] = null; // clear to let GC do its work
}

执行流程：

找到第一个等于指定元素值的元素；
快速删除；
fastRemove(int index)相对于remove(int index)少了检查索引越界的操作，可见jdk将性能优化到极致。

retainAll(Collection c)求两个集合的交集

/**
 * 求两个集合的交集
 * Retains only the elements in this list that are contained in the
 * specified collection.  In other words, removes from this list all
 * of its elements that are not contained in the specified collection.
 *  * @param c collection containing elements to be retained in 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">opti
 * @throws NullPointerException if this list contains a null element and the
 *                              specified collection does not permit null elements
 *                              (<a href="Collection.html#optional-restrictions">opti
 *                              or if the specified collection is null
 * @see Collection#contains(Object)
 */
public boolean retainAll(Collection<?> c) {
    // 集合c不能为null
    Objects.requireNonNull(c);
    // 调用批量删除方法，这时complement传入true，表示删除不包含在c中的元素
    return batchRemove(c, true);
}
/**
 * 批量删除元素
 * complement为true表示删除c中不包含的元素
 * complement为false表示删除c中包含的元素
 * @param c
 * @param complement
 * @return
 */
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    /**
     * 使用读写两个指针同时遍历数组
     * 读指针每次自增1，写指针放入元素的时候才加1
     * 这样不需要额外的空间，只需要在原有的数组上操作就可以了
     */
    int r = 0, w = 0;
    boolean modified = false;
    try {
        // 遍历整个数组，如果c中包含该元素，则把该元素放到写指针的位置（以complement为准）
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // 正常来说r最后是等于size的，除非c.contains()抛出了异常
        if (r != size) {
            // 如果c.contains()抛出了异常，则把未读的元素都拷贝到写指针之后
            System.arraycopy(elementData, r,
                    elementData, w,
                    size - r);
            w += size - r;
        }
        if (w != size) {
            // 将写指针之后的元素置为空，帮助GC
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            // 新大小等于写指针的位置（因为每写一次写指针就加1，所以新大小正好等于写指针的位置）
            size = w;
            modified = true;
        }
    }
    // 有修改返回true
    return modified;
}

执行流程：

遍历elementData数组；

如果元素在c中，则把这个元素添加到elementData数组的w位置并将w位置往后移一位；

遍历完之后，w之前的元素都是两者共有的，w之后（包含）的元素不是两者共有的；

将w之后（包含）的元素置为null，方便GC回收；

removeAll(Collection c)求两个集合的单方向差集

求两个集合的单方向差集，只保留当前集合中不在c中的元素，不保留在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) {
    // 集合c不能为空
    Objects.requireNonNull(c);
    // 同样调用批量删除方法，这时complement传入false，表示删除包含在c中的元素
    return batchRemove(c, false);
}

与retainAll(Collection c)方法类似，只是这里保留的是不在c中的元素。

6.扩展知识

ArrayList所使用的toString()方法分析：

我们都知道ArrayList集合是可以直接使用toStrin()方法的，那么我们来挖一下ArrayList的toString方法如何实现的：

在ArrayList源码中并没有直接的toString()方法，我们需要到其父类AbstractList的父类AbstractCollection中寻找：

/**
 * Returns a string representation of this collection.  The string
 * representation consists of a list of the collection's elements in the
 * order they are returned by its iterator, enclosed in square brackets
 * (<tt>"[]"</tt>).  Adjacent elements are separated by the characters
 * <tt>", "</tt> (comma and space).  Elements are converted to strings as
 * by {@link String#valueOf(Object)}.
 *
 * @return a string representation of this collection
 */
public String toString() {
    Iterator<E> it = iterator();// 获取迭代器
    if (! it.hasNext())//如果为空直接返回
        return "[]";
    // StringBuilder进行字符串拼接
    StringBuilder sb = new StringBuilder();
    sb.append('[');
    for (;;) {// 无限循环 == while(true)
        E e = it.next();// 迭代器 next方法取元素，并将光标后移
        sb.append(e == this ? "(this Collection)" : e);// 三元判断
        if (! it.hasNext())
            return sb.append(']').toString();// 没有元素了，则拼接右括号
        sb.append(',').append(' ');// 还有元素存在
    }
}

<br>
### 7. **总结**
（1）ArrayList内部使用数组存储元素，当数组长度不够时进行扩容，每次加一半的空间，ArrayList不会进行缩容；
（2）ArrayList支持随机访问，通过索引访问元素极快，时间复杂度为O(1)；
（3）ArrayList添加元素到尾部极快，平均时间复杂度为O(1)；
（4）ArrayList添加元素到中间比较慢，因为要搬移元素，平均时间复杂度为O(n)；
（5）ArrayList从尾部删除元素极快，时间复杂度为O(1)；
（6）ArrayList从中间删除元素比较慢，因为要搬移元素，平均时间复杂度为O(n)；
（7）ArrayList支持求并集，调用addAll(Collection c)方法即可；
（8）ArrayList支持求交集，调用retainAll(Collection c)方法即可；
（7）ArrayList支持求单向差集，调用removeAll(Collection c)方法即可；
<br>
>答疑问题：
**elementData设置成了transient，那ArrayList是怎么把元素序列化的呢**？
```java
/**
 * Save the state of the <tt>ArrayList</tt> instance to a stream (that
 * is, serialize it).
 * 将<tt> ArrayList </ tt>实例的状态保存到流中（即，对其进行序列化）
 *
 * @serialData The length of the array backing the <tt>ArrayList</tt>
 * instance is emitted (int), followed by all of its elements
 * (each an <tt>Object</tt>) in the proper order.
 */
private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
    // 防止序列化期间有修改
    int expectedModCount = modCount;
    // 写出非transient非static属性（会写出size属性）
    s.defaultWriteObject();
    // 写出元素个数
    s.writeInt(size);
    // 依次写出元素
    for (int i = 0; i < size; i++) {
        s.writeObject(elementData[i]);
    }
    // 如果有修改，抛出异常
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}
/**
 * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
 * deserialize it).
 * 从流中重构<tt> ArrayList </ tt>实例（即,反序列化）
 */
private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
    // 声明为空数组
    elementData = EMPTY_ELEMENTDATA;
    // 读入非transient非static属性（会读取size属性）
    s.defaultReadObject();
    // 读入元素个数，没什么用，只是因为写出的时候写了size属性，读的时候也要按顺序来读
    s.readInt(); // ignored
    if (size > 0) {
        // 计算容量
        int capacity = calculateCapacity(elementData, size);
        SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
        // 检查是否需要扩容
        ensureCapacityInternal(size);
        Object[] a = elementData;
        // 依次读取元素到数组中
        for (int i = 0; i < size; i++) {
            a[i] = s.readObject();
        }
    }
}

查看writeObject()方法可知，先调用s.defaultWriteObject()方法，再把size写入到流中，再把元素一个一个的写入到流中。

一般地，只要实现了Serializable接口即可自动序列化，writeObject()和readObject()是为了自己控制序列化的方式，这两个方法必须声明为private，在java.io.ObjectStreamClass#getPrivateMethod()方法中通过反射获取到writeObject()这个方法。

在ArrayList的writeObject()方法中先调用了s.defaultWriteObject()方法，这个方法是写入非static非transient的属性，在ArrayList中也就是size属性。同样地，在readObject()方法中先调用了s.defaultReadObject()方法解析出了size属性。

elementData定义为transient的优势，自己根据size序列化真实的元素，而不是根据数组的长度序列化元素，减少了空间占用。

7.ArrayList相关面试题

7.1 ArrayList如何扩容？

第一次扩容10，以后每次都扩容原容量的1.5倍，扩容通过位运算右移动1位。

7.2 ArrayList 频繁扩容导致添加性能急剧下降，如何处理？

直接上代码：

@Test
public void test06() {
    // ArrayList 频繁扩容导致添加性能急剧下降，如何处理？
    // 案例如下：
    ArrayList arrayList = new ArrayList();
    long startTime = System.currentTimeMillis();
    // 添加100w条数据到集合中
    for (int i = 0; i < 1000000; i++) {
        arrayList.add(i);
    }
    long endTime = System.currentTimeMillis();
    System.out.println("优化之前，添加100万条数据用时：" + (endTime - startTime));
    System.out.println("---------------下边是解决方案：------------------");
    ArrayList arrayList2 = new ArrayList(1000000);
    startTime = System.currentTimeMillis();
    // 添加100w条数据到集合中
    for (int i = 0; i < 1000000; i++) {
        arrayList2.add(i);
    }
    endTime = System.currentTimeMillis();
    System.out.println("优化之后，添加100万条数据用时：" + (endTime - startTime));
}

输出结果：

优化之前，添加10万条数据用时：58
---------------下边是解决方案：------------------
优化之后，添加10万条数据用时：13

以看出，如果在大量数据需要添加到集合中的时候，提前定义ArrayList集合的初始容量，从而不用花费大量时间在自动扩容上

7.3 ArrayList插入或删除元素是否一定比LinkedList慢？

从二者底层数据结构上来说：

ArrayList是实现了基于动态数组的数据结构

LinkedList基于链表的数据结构。

效率对比：

首部插入：LinkedList首部插入数据很快，因为只需要修改插入元素前后节点的prev值和next值即可。ArrayList首部插入数据慢，因为数组复制的方式移位耗时多。

中间插入：LinkedList中间插入数据慢，因为遍历链表指针（二分查找）耗时多；ArrayList中间插入数据快，因为定位插入元素位置的速度快，移位操作的元素没那么多。

尾部插入：LinkedList尾部插入数据慢，因为遍历链表指针（二分查找）耗时多；ArrayList尾部插入数据快，为定位插入元素位置的速度快，插入后移位操作的数据量少；

总结：

在集合里面插入元素速度比对结果是：首部插入，LinkedList更快；中间和尾部插入，ArrayList更快；

在集合里面删除元素类似，首部删除，LinkedList更快；中间删除和尾部删除，ArrayList更快；

因此，数据量不大的集合，主要进行插入、删除操作，建议使用LinkedList；数据量大的集合，使用ArrayList就可以了，不仅查询速度快，并且插入和删除效率也相对较高。

7.4 ArrayList 是线程安全的吗？

答案肯定是否的，我们来看一个例子：

首先新建一个线程任务类：

/**
 * @Auther: csp1999
 * @Date: 2020/10/29/18:25
 * @Description: 线程任务类
 */
public class CollectionTask implements Runnable {
    // 共享集合
    private List<String> list;
    public CollectionTask(List<String> list){
        this.list = list;
    }
    @Override
    public void run() {
        try {
            Thread.sleep(50);
        }catch (InterruptedException e){
            e.printStackTrace();
        }
        // 把当前线程名字加入到集合中
        list.add(Thread.currentThread().getName());
    }
}

接下来进行测试：

/**
 * @Auther: csp1999
 * @Date: 2020/10/29/18:28
 * @Description: ArrayList 线程安全性测试类
 */
public class Test01 {
    public static void main(String[] args) throws InterruptedException {
        // 创建集合
        List<String> list = new ArrayList<>();
        // 创建线程任务
        CollectionTask collectionTask = new CollectionTask(list);
        // 开启50条线程
        for (int i = 0; i < 50; i++) {
            new Thread(collectionTask).start();
        }
        // 确保子线程执行完毕
        Thread.sleep(3000);
        /**
         * 如果ArrayList是线程安全的，则遍历集合可以得到50条数据，
         * 打印集合长度为50
         * 否则说明其不是线程安全的！
         */
        // 遍历集合
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
        System.out.println("-------------------------------------");
        System.out.println("集合长度："+list.size());
    }
}

测试结果：

null
null
null
Thread-0
Thread-4
Thread-6
Thread-2
Thread-17
Thread-18
Thread-15
Thread-16
Thread-10
Thread-13
Thread-12
Thread-9
Thread-11
Thread-27
Thread-28
Thread-25
Thread-29
Thread-24
Thread-21
Thread-26
Thread-22
Thread-23
Thread-20
Thread-40
Thread-37
Thread-39
Thread-38
Thread-41
Thread-35
Thread-34
null
Thread-31
Thread-33
Thread-32
Thread-49
Thread-46
Thread-47
Thread-48
Thread-43
Thread-42
Thread-45
Thread-44
-------------------------------------
集合长度：45
Process finished with exit code 0

因此，得出结论，ArrayList并不是线程安全的集合！如果需要保证线程安全，建议使用Vector集合，其是线程安全的，但是相对于ArrayList来说，效率比较低。

而Vector相对于ArrayList之所以是线程安全的，就在于其add()为集合添加元素的方法：

// 可以看出Vector的add方法加上了synchronized 同步关键字
public synchronized void addElement(E obj) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
}

除了Vector集合外，还可以使用为如下方式

List<String> list = new ArrayList<>();
List<String> synchronizedList = Collections.synchronizedList(list);

这样得到的synchronizedList也是线程安全的！

注意：什么情况下不用给ArrayList加同步锁呢？

第一，在单线程情况下不需要加锁，为效率问题考虑！

第二，当ArrayList作为局部变量的时候不需要加锁，因为局部变量属于某一线程，而我们上述例子中是吧ArrayList作为成员变量来使用，成员变量的集合是需要被所有线程共享的，这是需要加锁！

7.5 如何复制某个ArrayList到另外一个ArrayList中去呢？你能列举几种？

使用clone()方法，因为ArrayList实现了Cloneable接口，可以被克隆

使用ArrayList构造方法，ArrayList(Collection c)

使用addAll(Collection c)方法

自己写循环去一个一个add()

7.6 ArrayList如何做到并发修改，而不出现并发修改异常？

问题：已知成员变量集合存储N多用户名称，在多线程的环境下，使用迭代器在读取集合数据的同时，如何保证还可以正常的写入数据到集合？

新建一个线程任务类：

/**
 * @Auther: csp1999
 * @Date: 2020/10/29/19:07
 * @Description: 线程任务类，使用ArrayList在多线程环境下，修改集合数据，
 * 且不出现并发修改异常
 */
public class CollectionThread implements Runnable{
    private static ArrayList<String> list = new ArrayList<>();
    static {
        list.add("Jack");
        list.add("Amy");
        list.add("Lucy");
    }
    @Override
    public void run() {
        for (String value : list){
            System.out.println(value);
            // 在读取数据的同时又向集合写入数据
            list.add("Coco");// 会出现并发修改异常
        }
    }
}

测试在多线程条件下读取共享集合数据的同时向其写入：

/**
 * @Auther: csp1999
 * @Date: 2020/10/29/19:10
 * @Description: 面试问题：
 * 已知成员变量集合存储N多用户名称，在多线程的环境下，使用迭代器在读取集合数据的同时，
 * 如何保证还可以正常的写入数据到集合？
 */
public class Test03 {
    public static void main(String[] args) {
        // 创建线程任务
        CollectionThread collectionThread = new CollectionThread();
        // 开启10条线程
        for (int i = 0; i < 10; i++) {
            new Thread(collectionThread).start();
        }
    }
}

测试结果：

Jack
Jack
Jack
Jack
Jack
Jack
Jack
Jack
Jack
Jack
Exception in thread "Thread-0" Exception in thread "Thread-1" Exception in thread "Thread-4" Exception in thread "Thread-5" Exception in thread "Thread-8" java.util.ConcurrentModificationException
  at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
  at java.util.ArrayList$Itr.next(ArrayList.java:859)
  at com.haust.list.CollectionThread.run(CollectionThread.java:21)
  at java.lang.Thread.run(Thread.java:748)
Exception in thread "Thread-9" java.util.ConcurrentModificationException
  at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
  at java.util.ArrayList$Itr.next(ArrayList.java:859)
  at com.haust.list.CollectionThread.run(CollectionThread.java:21)
  at java.lang.Thread.run(Thread.java:748)
Exception in thread "Thread-2" java.util.ConcurrentModificationException
  at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
  at java.util.ArrayList$Itr.next(ArrayList.java:859)
  at com.haust.list.CollectionThread.run(CollectionThread.java:21)
  at java.lang.Thread.run(Thread.java:748)
java.util.ConcurrentModificationException
  at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
  at java.util.ArrayList$Itr.next(ArrayList.java:859)
  at com.haust.list.CollectionThread.run(CollectionThread.java:21)
  at java.lang.Thread.run(Thread.java:748)
java.util.ConcurrentModificationException
  at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
  at java.util.ArrayList$Itr.next(ArrayList.java:859)
  at com.haust.list.CollectionThread.run(CollectionThread.java:21)
  at java.lang.Thread.run(Thread.java:748)
java.util.ConcurrentModificationException
  at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
  at java.util.ArrayList$Itr.next(ArrayList.java:859)
  at com.haust.list.CollectionThread.run(CollectionThread.java:21)
  at java.lang.Thread.run(Thread.java:748)
java.util.ConcurrentModificationException
  at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
  at java.util.ArrayList$Itr.next(ArrayList.java:859)
  at com.haust.list.CollectionThread.run(CollectionThread.java:21)
  at java.lang.Thread.run(Thread.java:748)
Exception in thread "Thread-7" Exception in thread "Thread-6" java.util.ConcurrentModificationException
  at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
  at java.util.ArrayList$Itr.next(ArrayList.java:859)
  at com.haust.list.CollectionThread.run(CollectionThread.java:21)
  at java.lang.Thread.run(Thread.java:748)
Exception in thread "Thread-3" java.util.ConcurrentModificationException
  at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
  at java.util.ArrayList$Itr.next(ArrayList.java:859)
  at com.haust.list.CollectionThread.run(CollectionThread.java:21)
  at java.lang.Thread.run(Thread.java:748)
java.util.ConcurrentModificationException
  at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
  at java.util.ArrayList$Itr.next(ArrayList.java:859)
  at com.haust.list.CollectionThread.run(CollectionThread.java:21)
  at java.lang.Thread.run(Thread.java:748)

出现并发修改异常，为解决此问题呢，java引入了一个可以保证读和写都是线程安全的集合(读写分离集合)：CopyOnWriteArrayList

所以解决方案就是：

  ...
  // private static ArrayList<String> list = new ArrayList<>();
    // 使用读写分离集合替换掉原来的ArrayList
    private static CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
    static {
        list.add("Jack");
        list.add("Amy");
        list.add("Lucy");
    }
    @Override
    public void run() {
        for (String value : list){
            System.out.println(value);
            // 在读取数据的同时又向集合写入数据
            list.add("Coco");// 会出现并发修改异常
        }
    }

成功解决并发修改异常！

7.7 ArrayList和LinkedList 的区别？

ArrayList

基于动态数组的数据结构

对于随机访问的get和set，其效率优于LinkedList

对于随机操作的add和remove，ArrayList不一定比LinkedList慢(ArrayList底层由于是动态数组，因此并不是每一次add和remove都需要创建新数组)

LinkedList

基于链表的数据结构

对于顺序操作，LinkedList 不一定比ArrayList慢

对于随机操作，LinkedList 效率明显低于LinkedList

JDK集合源码之ArrayList解析(附带面试题举例)

1. ArrayList 继承体系

3. ArrayList 属性

5. ArrayList 相关操作方法

add(E e)添加元素到集合中

addAll(Collection c)添加所有集合参数中的所有元素

get(int index)获取指定索引位置的元素

retainAll(Collection c)求两个集合的交集

7.2 ArrayList 频繁扩容导致添加性能急剧下降，如何处理？

热门文章

最新文章

相关课程

相关电子书

相关实验场景

推荐镜像

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

JDK集合源码之ArrayList解析(附带面试题举例)

1. ArrayList 继承体系

3. ArrayList 属性

5. ArrayList 相关操作方法

add(E e)添加元素到集合中

addAll(Collection c)添加所有集合参数中的所有元素

get(int index)获取指定索引位置的元素

retainAll(Collection c)求两个集合的交集

7.2 ArrayList 频繁扩容导致添加性能急剧下降，如何处理？

热门文章

最新文章

相关课程

相关电子书

相关实验场景

推荐镜像