五、Collection 子接口之 List


存取有序、可以存放重复的元素。

5.1 List 接口

01、List

java.util.List 接口继承自 Collection 接口，是单列集合的一个重要分支，习惯性地会将实现了 List 接口的对象称为 List 集合。在 List 集合中允许出现重复的元素，所有的元素是以一种线性方式进行存储的，在程序中可以通过索引来访问集合中的指定元素。另外，List 集合还有一个特点就是元素有序，即元素的存入顺序和取出顺序一致。

02、特点

  1. 它是一个元素存取有序的集合。例如，存元素的顺序是 11、22、33。那么集合中，元素的存储就是按照 11、 22、33 的顺序完成的）。
  2. 它是一个带有索引的集合，通过索引就可以精确的操作集合中的元素（与数组的索引是一个道理）。
  3. 集合中可以有重复的元素，可以通过元素的 equals 方法，来比较是否为重复的元素。

03、List 接口中常用的方法

List 作为 Collection 集合的子接口，不但继承了 Collection 接口中的全部方法，而且还增加了一些根据元素索引来操作集合的特有方法：

  1. public void add(int index, E element) : 将指定的元素添加到该集合中的指定位置上。
  2. public E get(int index) :返回集合中指定位置的元素。
  3. public E remove(int index) : 移除列表中指定位置的元素, 返回的是被移除的元素。
  4. public E set(int index, E element) :用指定元素替换集合中指定位置的元素,返回值的更新前的元素。
public class list {
   public static void main(String[] args) {
       // 创建集合对象
       List<String> list = new ArrayList<>();
       // 添加元素
       list.add("Hello");
       list.add("Java");
       list.add("World");
       
       // 1.public E get(int index) :返回指定索引的元素
       System.out.println("get:"+list.get(0));
       System.out.println("get:"+list.get(1));
       System.out.println("get:"+list.get(2));
       
       // 2.public int size():返回集合中的元素的个数
       System.out.println("size:"+list.size());
       
       // 3.public E remove(int index):删除指定索引处的元素，返回被删除的元素
       System.out.println("remove:"+list.remove(0));
       
       // 4.public E set(int index, E element) :用指定元素替换集合中指定位置的元素,返回值的更新前的元素。
       list.set(1,"JSP");
       System.out.println("set:"+list);
       
       // 5.遍历输出
       for (String s:list){
           System.out.println(s);
       }
  }
}

5.2 ArrayList

ArrayList 实现了 List 接口，并且是基于数组实现的。

数组的大小是固定的，一旦创建的时候指定了大小，就不能再调整了。也就是说，如果数组满了，就不能再添加任何元素了。ArrayList 在数组的基础上实现了自动扩容，并且提供了比数组更丰富的预定义方法（各种增删改查），非常灵活。

元素增删慢，查找快，由于日常开发中使用多的功能为查询数据、遍历数据，所以 ArrayList 是常用的集合。

01、构造方法（创建 ArrayList）

创建 ArrayList 有两个方法：有参构造方法和无参构造方法：

方法 描述
ArrayList() 构造一个初始容量为 10 的空列表
ArrayList(int initialCapacity) 构造具有指定初始容量的空列表
ArrayList(Collection<? extends E> c) 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序

无参构造方法——ArrayList()

创建一个字符串类型的 ArrayList （通过尖括号来限定 ArrayList 中元素的类型，如果尝试添加其他类型的元素，将会产生编译错误）：

ArrayList<String> arrayList = new ArrayList<String>();

由于 ArrayList 实现了 List 接口，所以 arrayList 变量的类型也可以是 List 类型：

List<String> arrayList = new ArrayList<>();

这时，new 关键字声明后的尖括号内可以不再指定元素的类型，因为编译器可以通过前面尖括号中的类型进行智能推断。

扒一下 ArrayList() 方法的源码：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
	// 默认初始容量
	private static final int DEFAULT_CAPACITY = 10;

	// 默认空容量的数组，长度为 0
	/**
     * 用于默认大小的空实例的共享空数组实例。我们
     * 将此与 EMPTY_ELEMENTDATA 区分开来，以了解
     * 添加第一个元素时要膨胀多少。
     */
	private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
	
	// 集合真正存储数据的数组容器
	/**
     * 存储 ArrayList 元素的数组缓冲区。ArrayList 的容量就是这个数组缓冲区的长度。
     * 任何带有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList 将在添加第一个元素时扩展为 DEFAULT_CAPACITY。
     */
	transient Object[] elementData;
	
	// 无参构造方法
	public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
}

有参构造方法——ArrayList(int initialCapacity)

另外，如果非常确定 ArrayList 中元素的个数，在创建的时候还可以指定初始大小：

List<String> arrayList = new ArrayList<>(20);

这样做的好处是：可以有效地避免在添加新的元素时进行不必要的扩容。但是通常情况下，我们很难确定 ArrayList 中元素的个数，因此一般不指定初始大小。

扒一下 ArrayList(int initialCapacity) 方法的源码：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
	// 默认初始容量
	private static final int DEFAULT_CAPACITY = 10;

	// 长度为 0 的空数组
	private static final Object[] EMPTY_ELEMENTDATA = {};
	
	// 集合真正存储数据的数组容器
	/**
     * 存储 ArrayList 元素的数组缓冲区。ArrayList 的容量就是这个数组缓冲区的长度。
     * 任何带有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList 将在添加第一个元素时扩展为 DEFAULT_CAPACITY。
     */
	transient Object[] elementData;
	
	// 有参构造方法
	public ArrayList(int initialCapacity) {
		// 初始容量大于0
        if (initialCapacity > 0) {
        	// 创建 initialCapacity 大小的数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
        	// 创建空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
        	// 初始容量小于0，抛出异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
}

有参构造方法——ArrayList(Collection<? extends E> c)

构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回顺序：

/**
 * @author QHJ
 * @date 2022/9/22  10:52
 * @description: List 集合
 */
public class ListTest {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("aaa");
        list.add("bbb");
        list.add("ccc");

        ArrayList<String> list1 = new ArrayList<>(list);

        for (String s : list1){
            System.out.println(s);
        }
    }
}

扒一下 ArrayList(Collection<? extends E> c) 的源码：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
	// 长度为 0 的空数组
	private static final Object[] EMPTY_ELEMENTDATA = {};

	// 集合的长度
	private int size;
	
	// 集合真正存储数据的数组容器
	/**
     * 存储 ArrayList 元素的数组缓冲区。ArrayList 的容量就是这个数组缓冲区的长度。
     * 任何带有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList 将在添加第一个元素时扩展为 DEFAULT_CAPACITY。
     */
	transient Object[] elementData;
	
	// 有参构造方法
	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;
        }
    }

	// 将集合转数组的方法
	public Object[] toArray() {
		// 调用数组工具类的方法
        return Arrays.copyOf(elementData, size);
    }
}

class Arrays{
	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")
        // 不管三元运算符的结果如何，都会创建一个新的数组
        // 新数组的长度一定和集合的 size 一样
        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;
    }
}

总结：以无参构造方法创建 ArrayList 的时候，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。

补充：JDK 6 new 无参构造的 ArrayList 对象时，直接创建了长度为 10 的 object[ ] 数组 elementData。

02、添加方法(向 ArrayList 中添加元素)

向 ArrayList 中添加元素有四种方法：

方法名 描述
public boolean add(E e); 将指定的元素追加到此列表的末尾
public void add(int index, E element); 在此列表中的指定位置插入指定的元素
public boolean addAll(Collection<? extends E> c); 按指定集合的 Iterator 返回的顺序将指定集合汇总的所有元素追加到此列表的末尾
public boolean addAll(int index, Collection<? extends E> c); 将指定集合中的所有元素插入到此列表中，从指定的位置开始

add(E e)

通过 add() 方法向 ArrayList 中添加一个元素，如果不指定下标的话，就默认添加在末尾：

arrayList.add("青花椒");

add() 方法在添加元素的时候会判断需不需要进行扩容，扒一下 add(E e) 方法的源码：

// 默认的容量
private static final int DEFAULT_CAPACITY = 10;

// 长度为 0 的空数组
private static final Object[] EMPTY_ELEMENTDATA = {};

// 默认容量为空的数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 集合真正存储数据的数组容器
transient Object[] elementData;

// 集合的长度
private int size;

/**
 * 将指定的元素追加到此列表的末尾
 **/
public boolean add(E e) {
	// size 初始化是 0
	// 添加元素之前先调用 ensureCapacityInternal() 方法
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 实际上就是为数组赋值
    elementData[size++] = e;
    return true;
}

add(E e) 方法里调用了私有的 ensureCapacityInternal(int minCapacity)方法：

如果一开始创建 ArrayList 的时候没有指定大小，elementData 就会被初始化成一个空的数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

然后进入到 if 分支后，minCapacity 的值就会等于 DEFAULT_CAPACITY。

也就是说，当要 add 进第一个元素时，传入的 minCapacity 为 1，在 Math.max() 方法比较后，minCapacity 为 10。

// 得到最小扩容量
private void ensureCapacityInternal(int minCapacity) {
	// 判断集合是否为空
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    	// 将默认容量和集合长度中的最大值赋值给集合长度
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

ensureCapacityInternal(int minCapacity) 方法里调用了 ensureExplicitCapacity(int minCapacity)方法：

// 判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
	// 增量，指实际修改集合的次数
    modCount++;

    // overflow-conscious code
    // 判断最小需要容量(minCapacity)是否大于实际存储数据的数组长度(elementData)
    // 是——>需要扩容
    // 否——>不需要扩容
    // 只有容量不够的情况下才会调用核心扩容方法
    // 扩容扩的是实际存储数据的数组长度
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

JDK11 移除了 ensureCapacityInternal() 和 ensureExplicitCapacity() 方法。

ensureExplicitCapacity(int minCapacity) 方法里调用了 grow(int minCapacity)方法：

/**
 * 要分配的最大数组大小
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
/**
 * ArrayList扩容的核心方法。
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // >>：右移几位，就相当于除以 2 的几次幂
    // <<：左移几位，就相当于乘以 2 的几次幂
    // 扩容的核心算法：原容量的 1.5 倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 扩容的新容量比最小的容量还小，说明扩容得到的新容量并不理想
    if (newCapacity - minCapacity < 0)
    	// 就将最小需要容量复制给新容量
        newCapacity = minCapacity;
    // 新的容量远远大于最大容量(21447483639)，就调用hugeCapacity(minCapacity);方法
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // 数组扩容
    elementData = Arrays.copyOf(elementData, newCapacity);
}

int newCapacity = oldCapacity + (oldCapacity >> 1)，所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右（oldCapacity 为偶数就是 1.5 倍，否则是 1.5 倍左右）。奇偶不同，比如 ：10+10/2 = 15，33+33/2=49，如果是奇数的话会丢掉小数。

grow() 方法中调用了 hugeCapacity()方法：、

从 grow() 方法的源码知道： 如果新容量大于 MAX_ARRAY_SIZE，进入(执行) hugeCapacity() 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，如果 minCapacity 大于最大容量，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8。

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // 对 minCapacity 和 MAX_ARRAY_SIZE 进行比较
    // 若 minCapacity 大，将 Integer.MAX_VALUE 作为新数组的大小
    // 若 MAX_ARRAY_SIZE 大，将 MAX_ARRAY_SIZE 作为新数组的大小
    // MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

也就是说，如果 ArrayList 在创建的时候没有指定大小，则默认可以容纳 10 个元素（第一次扩容，由原来的 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 扩容为容量为 10 的数组）；当添加到第 11 个元素时，会再次调用 grow() 方法进行自动扩容。

结论：底层使用了 Arrays.copyOf(elementData, newCapacity) 方法进行了扩容。

add(int index, E element)

除了 add(E e) 方法外，还可以通过 add(int index, E element) 方法把元素添加到指定的位置：

arrayList.add(0, "青花椒");

扒一下 add(int index, E element)方法的源码：

// 默认的容量
private static final int DEFAULT_CAPACITY = 10;

// 长度为 0 的空数组
private static final Object[] EMPTY_ELEMENTDATA = {};

// 默认容量为空的数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 集合真正存储数据的数组容器
transient Object[] elementData;

// 集合的长度
private int 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++;
}

add(int index, E element) 方法里调用了 rangeCheckForAdd(int index)方法：

private void rangeCheckForAdd(int index) {
	// 判断索引是否大于数组长度、是否小于 0
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

接着调用了调用了私有的 ensureCapacityInternal(int minCapacity)方法，这个过程和 add(E e) 方法中的调用过程是一样的。

然后会调用到一个非常重要的本地方法，它会对数组进行复制（要插入位置上的元素往后复制）：

System.arraycopy(elementData, index, elementData, index + 1, size - index);

第一个参数就是原数组（需要复制的数组），第二个参数是要复制的原数组中的起始位置（从哪里开始复制），第三个参数是目标数组（存元素的集合），第四个参数是要复制到的目标数组的起始位置（复制到哪个地方），第五个参数是要复制的元素的长度。
JavaSE进阶之（五）Collection 子接口之 List-小白菜博客
结论：底层使用了 System.arraycopy(elementData, index, elementData, index + 1, size - index) 方法进行扩容。

addAll(Collection<? extends E> c)

向 ArrayList 中添加一个集合，如果不指定下标的话，就默认添加在末尾。addAll(Collection<? extends E> c)方法就是将一个集合中的所有元素一次性地添加到另一个集合中：

ArrayList<String> arrayList = new ArrayList<String>();
ArrayList<String> list = new ArrayList<>();
list.add("aaa");
list.add("bbb");
list.add("ccc");

ArrayList<String> list1 = new ArrayList<>(list);
list1.addAll(arrayList);

扒一下 addAll(Collection<? extends E> c) 方法的源码：

// 默认的容量
private static final int DEFAULT_CAPACITY = 10;

// 长度为 0 的空数组
private static final Object[] EMPTY_ELEMENTDATA = {};

// 默认容量为空的数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 集合的长度
private int size;

// 集合真正存储数据的数组容器
transient Object[] elementData;

public boolean addAll(Collection<? extends E> c) {
	// 将集合转成数组
    Object[] a = c.toArray();
    // 将有数据的集合（数组）长度赋值给 numNew 
    int numNew = a.length;
    // 校验、扩容
    // size 代表新集合的长度，numNew 代表传入的集合的长度
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 真正拷贝的代码
    // 将原数组（a）拷贝到新数组（elementData）中
    System.arraycopy(a, 0, elementData, size, numNew);
    // 更新集合的长度
    size += numNew;
    // 根据 numNew 的值返回是否添加成功
    return numNew != 0;
}

结论：底层使用了 System.arraycopy() 方法进行拷贝。

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

向 ArrayList 中添加一个集合，addAll(int index, Collection<? extends E> c)方法就将一个集合中的所有元素一次性地添加到另一个集合中的指定位置：

ArrayList<String> list = new ArrayList<>();
list.add("aaa");
list.add("bbb");
list.add("ccc");

ArrayList<String> list1 = new ArrayList<>(list);
list1.add("ddd");
list1.add("eee");

list1.addAll(1, list);

扒一下 addAll(int index, Collection<? extends E> c)方法的源码：

// 默认的容量
private static final int DEFAULT_CAPACITY = 10;

// 长度为 0 的空数组
private static final Object[] EMPTY_ELEMENTDATA = {};

// 默认容量为空的数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 集合的长度
private int size;

// 集合真正存储数据的数组容器
transient Object[] elementData;

public boolean addAll(int index, Collection<? extends E> c) {
	// 校验索引
	// 判断索引是否大于数组长度、是否小于 0
    rangeCheckForAdd(index);

	// 将集合转成数组（数据源集合，也就是要添加的集合）
    Object[] a = c.toArray();
    // 将有数据的集合（数组）长度赋值给 numNew 
    int numNew = a.length;
    // 调用这个方法的目的就是为了给集合存储数据的数组进行扩容
    ensureCapacityInternal(size + numNew);  // Increments modCount

	// numMoved 代表数据目的中要移动的元素个数，size 代表数据目的中的数组长度
	// numMoved = 数据目的的长度-调用索引index
    int numMoved = size - index;
    // 判断需要移动的个数是否大于 0
    if (numMoved > 0)
    	// 调用此方法是对数据目的进行移动（从index开始到结尾）
    	// 使用 System 中的方法 arraycopy 进行移动
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

	// 真正将数据源（list）中的所有数据添加到目标集合中
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

在这里插入图片描述

结论：addAll(int index, Collection<? extends E> c) 方法进行了两次 System.arraycopy() 方法的调用。

03、修改方法(更新 ArrayList 中的元素)

ArrayList 使用 set() 方法来更新集合中的元素，需要提供下标和新元素：

ArrayList<String> arrayList = new ArrayList<String>();
arrayList.add("张三");
arrayList.add("李四");
arrayList.add("王五");
arrayList.set(1, "青花椒");

扒一下 set() 方法的源码：

// 默认的容量
private static final int DEFAULT_CAPACITY = 10;

// 长度为 0 的空数组
private static final Object[] EMPTY_ELEMENTDATA = {};

// 默认容量为空的数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 集合的长度
private int size;

// 集合真正存储数据的数组容器
transient Object[] elementData;

public E set(int index, E element) {
	// 校验索引
    rangeCheck(index);

	// 将数组中索引为 index 的值取出
    E oldValue = elementData(index);
    // 把要替换的值 element 存入到 elementData 数组的 index 位置
    elementData[index] = element;
    // 返回被替换的元素
    return oldValue;
}

其中，校验索引调用了私有的 rangeCheck(int index)方法：

private void rangeCheck(int index) {
	// 索引大于数组长度就抛出异常
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

04、获取方法(获取 ArrayList 中的元素)

ArrayList 使用 get()方法来根据索引获取元素，需要提供索引：

ArrayList<String> arrayList = new ArrayList<String>();
arrayList.add("张三");
arrayList.add("李四");
arrayList.add("王五");

arrayList.get(2);

扒一下 get()方法的源码：

// 集合真正存储数据的数组容器
transient Object[] elementData;

public E get(int index) {
	// 校验索引，与 set() 方法相同
    rangeCheck(index);

	// 根据索引获取数组(集合)中的元素
    return elementData(index);
}

05、删除方法(删除 ArrayList 中的元素)

ArrayList 中的 remove()方法用于删除指定下标位置上的元素，remove(Object o)方法用于删除指定值的元素：

ArrayList<String> arrayList = new ArrayList<String>();
arrayList.add("张三");
arrayList.add("李四");
arrayList.add("王五");

// 这两种方法都表示删除集合中的 "李四" 元素
arrayList.remove(1);
arrayList.remove("李四");

remove(int index)

扒一下 remove(int index)方法的源码：

public E remove(int index) {
	// 校验索引
    rangeCheck(index);

	// 增量，指实际修改集合的次数
    modCount++;
    // 将数组中索引为 index 的值取出
    E oldValue = elementData(index);

	// 要移动元素的个数
	// numMoved = 数组的长度 - 索引 - 本身(1)
    int numMoved = size - index - 1;
    if (numMoved > 0)
    	// 对数组进行复制移动
    	// （目标数组, 从index+1位开始, 结果数组, 移动到index位置, 要移动元素的个数）
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 把要删除的元素位置清空
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

remove(Object o)

扒一下 remove(Object o)方法的源码：

public boolean remove(Object o) {
	// 判断要删除的元素是否为 null
    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])) {
            	// 相等就直接删除（根据index删除）
                fastRemove(index);
                return true;
            }
    }
    return false;
}

remove(Object o) 方法中调用了 fastRemove(int index)方法：

// 集合真正删除元素的方法
private void fastRemove(int index) {
	// 增量，指实际修改集合的次数
    modCount++;
    // 要移动元素的个数
	// numMoved = 数组的长度 - 索引 - 本身(1)
    int numMoved = size - index - 1;
    if (numMoved > 0)
    	// 对数组进行复制移动
    	// （目标数组, 从index+1位开始, 结果数组, 移动到index位置, 要移动元素的个数）
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 把要删除的元素位置清空，就是为了尽快被垃圾回收机制回收
    elementData[--size] = null; // clear to let GC do its work
}

在这里插入图片描述

06、查找方法(查找 ArrayList 中的元素)

如果要正序查找一个元素，可以使用 indexOf()方法；如果要倒序查找一个元素，可以使用 lastIndexOf()方法：

ArrayList<String> arrayList = new ArrayList<String>();
arrayList.add("张三");
arrayList.add("李四");
arrayList.add("王五");

// 正序查找
arrayList.indexOf("李四");
// 倒序查找
arrayList.lastIndexOf("李四");

扒一下源码：

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;
}

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;
}

其实这两个方法是非常类似的，只是遍历顺序不同。

如果 ArrayList 中的元素是经过排序的，就可以使用二分查找法，效率会更快。

07、转换方法

ArrayList 中使用 toString()方法把集合中所有的数据转换成字符串：

ArrayList<String> arrayList = new ArrayList<String>();
arrayList.add("张三");
arrayList.add("李四");
arrayList.add("王五");

String str = arrayList.toString();
System.out.println(str);  // [张三, 李四, 王五]

扒一下 toString() 方法的源码：

public abstract class AbstractCollection<E> implements Collection<E> {
	public String toString() {
		// 获取迭代器
	    Iterator<E> it = iterator();
	    // 判断迭代器是否为空
	    if (! it.hasNext())
	        return "[]";
	
		// 创建 StringBuilder
	    StringBuilder sb = new StringBuilder();
	    // 首先追加 '['
	    sb.append('[');
	    // 无限循环
	    for (;;) {
	    	// 调用迭代器的 next() 方法取出元素，且将光标向下移动
	        E e = it.next();
	        // 三元判断
	        sb.append(e == this ? "(this Collection)" : e);
	        if (! it.hasNext())
	        	// 没有元素就在缓冲区的最后追加']'，且把整个缓冲区的数据转成字符串
	        	// 结束该方法
	            return sb.append(']').toString();
	        // 有元素就直接追加
	        sb.append(',').append(' ');
	    }
	}
}

08、清空方法

clear()方法用于清空集合中的所有数据：

ArrayList<String> arrayList = new ArrayList<String>();
arrayList.add("张三");
arrayList.add("李四");
arrayList.add("王五");

System.out.println("清空前的集合：" + arrayList); // 清空前的集合：[张三, 李四, 王五]
arrayList.clear();
System.out.println("清空后的集合：" + arrayList); // 清空后的集合：[]

扒一下 clear() 方法的源码：

public void clear() {
	// 实际修改次数自增
    modCount++;

	// 循环遍历集合，并清空数据
    // clear to let GC do its work
    for (int i = 0; i < size; i++)
    	// 把数组的每一个位置都置为 null，让垃圾回收期尽早地回收
        elementData[i] = null;

	// 数组长度置为0
    size = 0;
}

09、包含方法

ArrayList 集合中使用 contains()方法来判断集合是否包含指定元素：

ArrayList<String> arrayList = new ArrayList<String>();
arrayList.add("张三");
arrayList.add("李四");
arrayList.add("王五");

// 集合中如果没有赵六这个元素，就添加
if (!arrayList.contains("赵六")) {
    arrayList.add("赵六");
}

扒一下 contains()方法的源码：

public boolean contains(Object o) {
	// 根据 indexOf() 返回的结果和 0 进行比较
	// 如果大于等于 0，就说明找到了(包含了)；否则就说明没有找到(未包含)
    return indexOf(o) >= 0;
}

constains() 方法中调用了 indexOf()方法：

public int indexOf(Object o) {
	// 判断要找的元素是否为 null
    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;
}

10、判空方法(判断 ArrayList 集合是否为空)

isEmpty()方法用于判断集合是否为空：

ArrayList<String> arrayList = new ArrayList<String>();
arrayList.add("张三");
arrayList.add("李四");
arrayList.add("王五");

boolean b = arrayList.isEmpty();
System.out.println(b); // false

扒一下 isEmpty()方法的源码：

public boolean isEmpty() {
	// 根据集合的长度返回对应的结果
    return size == 0;
}

11、System.arraycopy() 和 Arrays.copyOf() 方法

ArrayList 中大量调用了这两个方法。在初始化时构造方法调用 Arrays.copyOf() 方法进行数组的扩容，在添加方法中调用 System.arraycopy() 方法进行数组的复制。

扒一下 System.arraycopy() 方法的源码：

// arraycopy 是一个 native 方法
/**
*   复制数组
* @param src 源数组
* @param srcPos 源数组中的起始位置
* @param dest 目标数组
* @param destPos 目标数组中的起始位置
* @param length 要复制的数组元素的数量
*/
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

再扒一下 Arrays.copyOf()方法的源码：

public static int[] copyOf(int[] original, int newLength) {
	// 申请一个新的数组
    int[] copy = new int[newLength];
	// 调用System.arraycopy，将源数组中的数据进行拷贝,并返回新的数组
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

由此可见，Arrays.copyOf() 方法内部实际调用了 System.arraycopy() 方法。

主要区别：
System.arraycopy() 方法需要目标数组，将原数组拷贝到自己定义的数组或者原数组里，而且可以选择拷贝的起点和长度，以及放入新数组中的位置。
而 Arrays.copyOf() 是系统自动在内部新建一个数组，并返回该数组。

12、ArrayList 增删改查的时间复杂度

  1. 通过下标（也就是 get(int index)）访问一个元素的时间复杂度为 O(1)，因为是直达的，无论数据增大多少倍，耗时都不变；
  2. 默认添加一个元素（调用add()方法时）的时间复杂度为 O(1)，因为是直接添加到数组末尾的，但需要考虑到数组扩容时消耗的时间；
  3. 删除一个元素（调用 remove(Object) 方法时）的时间复杂度为 O(n)，因为要遍历列表，数据量增大几倍，耗时也增大几倍；如果是通过下标删除元素时，要考虑到数组的移动和复制所消耗的时间；
  4. 查找一个未排序的列表时间复杂度为 O(n)（调用 indexOf() 或者 lastIndexOf() 方法时），因为要遍历列表；查找排序过的列表时间复杂度为 O(log n)，因为可以使用二分查找法，当数据增大 n 倍时，耗时增大 logn 倍（这里的 log 是以 2 为底的，每找一次排除一半的可能）。

13、总结

ArrayList 如果有中文名的话，应该叫动态数组，也就是可增长的数组，可调整大小的数组。动态数组克服了静态数组的限制，静态数组的容量是固定的，只能在首次创建的时候指定。而动态数组会随着元素的增加而自动调整大小，更符合实际的开发需求。

学习集合框架，ArrayList 是第一课，也是新手进阶的重要一课。要想完全掌握 ArrayList，扩容这个机制是必须得掌握，也是面试中经常考察的一个点。

要想掌握扩容机制，就必须得读源码，也就肯定会遇到 oldCapacity >> 1，有些初学者会选择跳过，虽然不影响整体上的学习，但也错过了一个精进的机会。

计算机内部是如何表示十进制数的，右移时又发生了什么，静下心来去研究一下，你就会发现，哦，原来这么有趣呢？

5.3 LinkedList

01、LinkedList 概述

链表是由一系列非连续的节点组成的存储结构，LinkedList 底层使用的是 双向链表 数据结构 (JDK 1.6 之前为循环链表，JDK 1.7 取消了循环)，它的随机访问效率比 ArrayList 低，顺序访问的效率比 ArrayList 高。每个节点都有一个前驱和一个后继。

双向链表和双向循环链表：

  • 双向链表

    包含两个指针，一个 prev 指向前一个节点，一个 next 指向后一个节点。
    在这里插入图片描述

  • 双向循环链表

    最后一个节点的 next 指向 head，而 head 的 prev 指向最后一个节点，构成一个环。
    在这里插入图片描述

为什么要使用链表呢？

举个例子：假如现在我的手头要管理一堆票据，可能有一张，也有可能有一亿张。该怎么办呢？

可以申请一个 10G 的大数组等着，但是万一票据只有 100 张呢？

申请一个默认大小的数组，随着数据量的增大扩容？但是扩容是需要重复复制数组的，很耗时间。

关键是，数组还有一个弊端，假如现在有 500 万张票据，现在要从中间删除一个票据，就需要把 250 万张票据往前移动一格。

遇到这种情况的时候，很显然 ArrayList 是最不正确的选择。这个时候就要使用链表来解决了。

链表大致分为三个层次：

  1. 第一层叫做单向链表，只有一个后指针，指向下一个数据；
  2. 第二层叫做双向链表，有两个指针，后指针指向下一个数据，前指针指向上一个数据；
  3. 第三层叫做二叉树，把后指针去掉，换成左右指针。

但是链表现在还达不到第三层。

02、 静态内部类 Node

LinkedList 类中有一个私有的静态内部类，叫做 Node，也就是节点：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
	// 静态内部类，创建节点
	private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}

它由三部分组成：

  1. 节点上的元素
  2. 下一个节点
  3. 上一个节点
    在这里插入图片描述
  • 对于第一个节点来说，prev 为 null；
  • 对于最后一个节点来说，next 为 null；
  • 其余的节点，prev 指向前一个，next 指向后一个。

03、LinkedList的常用方法

与 ArrayList 一样，LinkedList 也无外乎有 “增删改查” 四种方法。

构造方法(初始化)

在此之前，必须得初始化：

// 无参初始化
LinkedList<String> linkedList = new LinkedList<>();
// 有参初始化
LinkedList<String> linkedList1 = new LinkedList<>(linkedList);

扒一下构造方法的源码：

public LinkedList() {
}
    
public LinkedList(Collection<? extends E> c) {
	// 调用无参构造方法
    this();
    // 调用添加方法进行添加操作
    addAll(c);
}

由此可见，LinkedList 在初始化时没有默认大小，也不可以指定大小。有参构造方法里调用了无参构造方法后，再调用了添加方法。

添加方法

可以调用 add() 方法进行添加元素：

LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("青花椒");
linkedList.add("美丽的");
linkedList.add("程序猿");

扒一下 add() 方法的源码：

public boolean add(E e) {
    linkLast(e);
    return true;
}

add() 方法内部其实调用的是 linkedLast() 方法，也就是在链表的尾部添加：

// 指向最后一个节点的指针
transient Node<E> last;

void linkLast(E e) {
	// 先将队尾的节点 last 存放到临时变量 l 中
    final Node<E> l = last;
   	// 新建一个节点 newNode
    final Node<E> newNode = new Node<>(l, e, null);
    // last 指向新节点
    last = newNode;
    if (l == null)
    	// 如果最后一个节点为空，说明是第一次添加，first 就指向新节点
        first = newNode;
    else
    	// 否则指向最后一个节点的指针向后移动
    	// 否则就将新节点赋值给 last 的后继节点
        l.next = newNode;
    size++;
    modCount++;
}

添加元素：

  • 添加第一个元素的时候，first 和 last 都为 null。然后新建一个节点 newNode，它的 prev 和 next 也为 null。然后把 last 和 first 都赋值为 newNode。此时还不能称之为链表，因为前后节点都是断裂的：
    在这里插入图片描述

  • 添加第二个元素时，first 和 last 都指向的是第一个节点。然后创建一个节点 newNode，它的 prev 指向的是第一个节点"青花椒"，next 为 null。然后把第一个节点的 next 赋值为 newNode：

    在这里插入图片描述

  • 添加第三个元素时，first 指向的是第一个节点，last 指向的是最后一个节点。然后新建一个节点 newNode，它的 prev 指向的是第二个节点"美丽的"，next 为 null。然后把第二个节点的 next 赋值为 newNode：
    在这里插入图片描述

除了 add() 方法之外，新增方法还有另外两个：

  1. addFirst()方法将元素添加到第一位；
  2. addLast()方法将元素添加到末尾。
    扒一下 addFirst() 方法的源码：
public void addFirst(E e) {
    linkFirst(e);
}

addFirst() 方法内部其实调用的是 linkFirst() 方法：

// 指向第一个节点的指针
transient Node<E> first;

private void linkFirst(E e) {
	// 先将队首的节点 last 存放到临时变量 l 中
    final Node<E> f = first;
    // 新建一个节点 newNode
    final Node<E> newNode = new Node<>(null, e, f);
    // first 指向新节点
    first = newNode;
    if (f == null)
    	// 如果第一个节点为空，说明是第一次添加，last 就指向新节点
        last = newNode;
    else
    	// 否则就将新节点赋值给 first 的前驱节点
        f.prev = newNode;
    size++;
    modCount++;
}

linkFirst 负责把新的节点设为 first，并将新的 first 的 next 更新为之前的 first。

删除方法

LinkedList 的删除方法有：

  1. remove()：删除第一个节点
  2. remove(int index)：删除指定位置的节点
  3. remove(Object o)：删除指定元素的节点
  4. removeFirst()：删除第一个节点
  5. removeLast()：删除最后一个节点
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("青花椒");
linkedList.add("美丽的");
linkedList.add("程序猿");

linkedList.remove(); // 删除"青花椒"
linkedList.remove(2); // 删除"程序猿"
linkedList.remove("青花椒"); // 删除"青花椒"
linkedList.removeFirst(); // 删除"青花椒"
linkedList.removeLast(); // 删除"程序猿"

remove() 内部调用的是 removeFirst() 方法：

public E remove() {
    return removeFirst();
}

remove( int index) 内部调用的是 unlink() 方法，就是更新当前节点的 next 和 prev，然后把当前节点上的元素设为 null：

public E remove(int index) {
	// 校验索引
    checkElementIndex(index);
    return unlink(node(index));
}

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

remove(Objext o)方法内部也调用了 unlink() 方法，只不过在此之前要先找到元素所在的节点：

public boolean remove(Object o) {
   // 对象为空，必须使用 == 来判断
   if (o == null) {
   		// 对象为空，循环遍历找出空值所在节点
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
    	// 对象不为空，要使用 equals() 判断。equals()是不能用来判 null 的，会抛出 NoSuchElementException 异常。
    	// 对象不为空，循环遍历找到元素所在节点
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

removeFirst()方法内部调用的是 unlinkFirst()方法，unlinkFirst 负责的就是把第一个节点毁尸灭迹，并且捎带把后一个节点的 prev 置为 null：

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    // 将 first 节点的值置为 null
    f.item = null;
    f.next = null; // help GC
    // first 指针后移
    first = next;
    // 只有 first 这一个节点，last 也为 null
    if (next == null)
        last = null;
    else
    	// 把后一个节点的 prev 置为 null
        next.prev = null;
    size--;
    modCount++;
    return element;
}

removeLast()方法与 removeFirst() 相似，只不过删除的是最后一个节点。

修改方法

可以调用 set() 方法来更新元素，必须传入索引和要修改的元素：

LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("青花椒");
linkedList.add("美丽的");
linkedList.add("程序猿");

linkedList.set(1, "漂亮的");

扒一下 set() 方法的源码：

public E set(int index, E element) {
	// 校验索引
    checkElementIndex(index);
    // 根据索引查找节点
    Node<E> x = node(index);
    E oldVal = x.item;
    // 把原有节点的元素替换成新元素
    x.item = element;
    return oldVal;
}

set() 方法中调用了 node(int index) 方法：

Node<E> node(int index) {
    // assert isElementIndex(index);

	// 相当于长度/2，位运算比除法运算效率要高很多
	// 对下标进行初步判断：判断是靠近前半截还是后半截
    if (index < (size >> 1)) {
    	// 靠近前半截就从下标 0 开始遍历
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
    	// 靠近后半截，就从末尾开始遍历
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

查询方法

LinkedList 的查询方法有：

  1. indexOf(Object o)：查找某个元素所在的位置
  2. get(int index)：查找某个位置上的元素
  3. getFirst()：获取第一个元素
  4. getLast()：获取最后一个元素
  5. poll() 和 pollFirst()：用于删除并返回第一个元素(两个方法尽管名字不同，但是方法体是完全相同的)
  6. pollLast()：用于删除并返回最后一个元素
  7. peekFirst()：用于返回但不删除第一个元素
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("青花椒");
linkedList.add("美丽的");
linkedList.add("程序猿");

linkedList.indexOf("美丽的"); // 1
linkedList.get(2); // 程序猿
linkedList.getFirst(); // 青花椒
linkedList.getLast(); // 程序猿
linkedList.poll(); // 青花椒
linkedList.pollFirst(); // 青花椒
linkedList.pollLast(); // 程序猿
linkedList.peek(); // 青花椒

扒一下indexOf(Object o)方法的源码，其内部分为两种，一种是元素为 null 的时候，必须使用 == 来判断；一种是元素不为 null 的时候，要使用 equals() 来判断：

public int indexOf(Object o) {
    int index = 0;
    // 对象为空，必须使用 == 来判断
    if (o == null) {
    	// 对象为空，遍历循环找出空值所在节点
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
    	// 对象不为空，要使用 equals() 判断。equals()是不能用来判 null 的，会抛出 NoSuchElementException 异常。
    	// 对象不为空，循环遍历找到元素所在节点
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

接着扒 get()方法的源码，其内部还是调用的 node() 方法来查找节点上的元素：

public E get(int index) {
	// 校验索引
    checkElementIndex(index);
    // 根据索引查找节点上的元素
    return node(index).item;
}

5.4 ArrayList 和 LinkedList 的区别

01、如何实现？

ArrayList 是如何实现的？

ArrayList 继承了 AbstractList 抽象类，实现了 List、RandomAccess、Cloneable、Serializable 接口：
JavaSE进阶之（五）Collection 子接口之 List-小白菜博客
底层是基于数组实现的，并且实现了动态扩容：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final int DEFAULT_CAPACITY = 10;
    transient Object[] elementData;
    private int size;
}

ArrayList 还实现了 RandomAccess 接口，这是一个标记接口：

public interface RandomAccess {
}

看源码会发现，实际上 RandomAccess 接口中什么都没有定义，内部是空的，只是一个标识而已。标识实现了这个接口的类支持快速(通常是固定时间)随机访问，也就是说不需要遍历就可以通过下标（索引）直接访问到内存地址。比如 get() 方法：

public E get(int index) {
    Objects.checkIndex(index, size);
    return elementData(index);
}
E elementData(int index) {
    return (E) elementData[index];
}

ArrayList 实现了 RandomAccess 接口，而 LinkedList 没有实现，为什么呢？其实还是与底层的数据结构有关的。ArrayList 底层是数组，而 LinkedList 底层是链表。数组天然支持随机访问，时间复杂度为 O(1)，所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素，时间复杂度为 O(n)，所以不支持快速随机访问。

但是！RandomAccess 接口只是标识，并不是说 ArrayList 实现了 RandomAccess 接口才具有快速访问功能的。

ArrayList 还实现了 Cloneable接口，这表明 ArrayList 是支持拷贝的。ArrayList 内部的确也重写了 Object 类的 clone() 方法：

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);
    }
}

ArrayList 还实现了 Serializable 接口，同样是一个标记接口：

public interface Serializable {
}

内部也是空的，标记实现了这个接口的类支持序列化，Java 的序列化是指将对象转换成字节序列的形式来表示，这些字节序列中包含了对象的字段和方法，序列化后的对象可以被写到数据库、写到文件，也可以用于网络传输。

ArrayList 中的关键字段 elementData 使用了 transient 关键字修饰，这个关键字的作用就是让它修饰的字段不被序列化。

这时问题就出来了：一个类既然实现了 Serializable 接口，肯定是想要被序列化的，那为什么保存关键数据的 elementData 又不想被序列化呢？

这就要回想一下 ArrayList 的底层了。我们都知道，ArrayList 是基于数组实现的，我们也知道，数组是定长的。也就是说，数组一旦声明了，长度（容量）就是固定的。这就很麻烦，数组一旦装满了，既不能添加新的元素进来了。

但是，ArrayList 并不像数组那样，而是实现了动态扩容。一旦在添加元素的时候发现容量用满了 s == elementData.length，就按照原来数组的 1.5 倍左右进行扩容，扩容之后再将原有的数组复制到新分配的内存地址上Arrays.copyOf(elementData, newCapacity)。

动态扩容意味着什么呢？就意味着数组的实际大小可能永远无法被填满，总有多余出来空置的内存空间。

就比如说，默认的数组大小是 10，当添加第 11 个元素的时候，数组的长度扩容了 1.5 倍，也就是 15，意味着还有 4 个内存空间是闲置的。

序列化的时候，如果把整个数组都序列化的话，就多序列化了 4 个内存空间。当存储的元素数量非常非常多的时候，闲置的空间就非常非常大，序列化耗费的时间就会非常非常多。

于是，ArrayList 内部提供了两个私有方法：writeObject() 和 readObject()来完成序列化和反序列化：

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;

    // Read in size, and any hidden stuff
    s.defaultReadObject();

    // Read in capacity
    s.readInt(); // ignored

    if (size > 0) {
        // be like clone(), allocate array based upon size not capacity
        int capacity = calculateCapacity(elementData, size);
        SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
        ensureCapacityInternal(size);

        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

由此可见，writeObject() 方法中使用了 ArrayList 的实际大小 size 而不是数组的长度 elementData.length 来作为元素的上限进行序列化。

LinkedList 是如何实现的？

JavaSE进阶之（五）Collection 子接口之 List-小白菜博客
LinkedList 是一个继承自 AbstractSequentialList 的双向链表，因此它也可以被当做堆栈、队列或双端队列进行操作：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;
}

LinkedList 内部定义了一个 Node 节点，它包含 3 部分：元素内容 item，前引用 prev 和后引用 next：

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

LinkedList 还实现了 Cloneable 接口，这表明 LinkedList 是支持拷贝的。

LinkedList 还实现了 Serializable 接口，这表明 LinkedList 是支持序列化的。

但是，LinkedList 中的关键字段 size、first、last 都使用了 transient 关键字修饰，是因为 LinkedList 想按照自己的方式进行序列化：

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    // Write out any hidden serialization magic
    s.defaultWriteObject();

    // Write out size
    s.writeInt(size);

    // Write out all elements in the proper order.
    for (Node<E> x = first; x != null; x = x.next)
        s.writeObject(x.item);
}

LinkedList 在序列化的时候只保留了元素的内容 item，并没有保留元素的前后引用，这样就节省了不少内存。但是只保留元素内容，不保留前后引用，反序列化的时候怎么办？

@SuppressWarnings("unchecked")
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // Read in any hidden serialization magic
    s.defaultReadObject();

    // Read in size
    int size = s.readInt();

    // Read in all elements in the proper order.
    for (int i = 0; i < size; i++)
        linkLast((E)s.readObject());
}

void linkLast(E e) {
    final Node<E> l = last;
    // 新建一个节点 newNode
    final Node<E> newNode = new Node<>(l, e, null);
    // last 指向新节点
    last = newNode;
    if (l == null)
    	// 如果最后一个节点为空，说明是第一次添加，first 就指向新节点
        first = newNode;
    else
    	// 否则就将新节点赋值给 last 的后继节点
        l.next = newNode;
    size++;
    modCount++;
}

很明显，在反序列化时循环遍历每个元素，并调用 linkLast() 方法重新把链表链接起来，这样就恢复了链表序列化之前的顺序。

与 ArrayList 相比，LinkedList 没有实现 RandomAccess 接口，是因为 LinkedList 存储数据的内存地址是不连续的，所以不支持随机访问。

02、新增元素的速度？

ArrayList 新增

ArrayList 新增元素有两种情况：一种是直接将元素添加到数组末尾，一种是将元素插入到指定位置。

添加到数组末尾：

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

很简单，先判断是否需要扩容，然后直接通过索引将元素添加到末尾。

插入到指定位置：

public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index,
            elementData, index + 1,
            s - index);
    elementData[index] = element;
    size = s + 1;
}

先检查插入的位置是否在合理的范围之内，然后判断是否需要扩容，再把该位置以后的元素复制到新添加元素的位置之后，最后通过索引将元素添加到指定的位置。这种情况是非常伤的，性能会比较差。

LinkedList 新增

LinkedList 新增元素也有两种情况，一种是直接将元素添加到队尾，一种是将元素插入到指定位置。

添加到队尾：

public boolean add(E e) {
    linkLast(e);
    return true;
}
void linkLast(E e) {
	// 先将队尾的节点 last 存放到临时变量 l 中
    final LinkedList.Node<E> l = last;
    // 新建一个节点
    final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);
    // 将新节点赋值给 last
    last = newNode;
    if (l == null)
    	// 如果 l 为 null，说明是第一次添加，first 为新的节点
        first = newNode;
    else
    	// 否则将新的节点赋值给 last 的后继节点
        l.next = newNode;
    size++;
    modCount++;
}

先将队尾的节点 last 存放到临时变量 l 中，然后生成新的 Node 节点，并赋给 last，如果 l 为 null，说明是第一次添加，所以 first 为新的节点；否则将新的节点赋给之前 last 的 next。

插入到指定位置：

public void add(int index, E element) {
	// 校验索引
    checkPositionIndex(index);

    if (index == size)
    	// 添加到队尾
        linkLast(element);
    else
        linkBefore(element, node(index));
}
// 查找指定位置上的元素
LinkedList.Node<E> node(int index) {
    // assert isElementIndex(index);
	// 判断插入的位置是前半截还是后半截
    if (index < (size >> 1)) {
        LinkedList.Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        LinkedList.Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
void linkBefore(E e, LinkedList.Node<E> succ) {
    // assert succ != null;
    // 先将 succ 的前一个节点存到临时变量中
    final LinkedList.Node<E> pred = succ.prev;
    // 生成新的节点
    final LinkedList.Node<E> newNode = new LinkedList.Node<>(pred, e, succ);
    // 将 succ 的前一个节点变更为 newNode
    succ.prev = newNode;
    if (pred == null)
    	// 说明插入的是队头，所以 first 为新节点
        first = newNode;
    else
    	// 否则将 prev 的后一个节点变更为 newNode
        pred.next = newNode;
    size++;
    modCount++;
}

先检查插入的位置是否在合理的范围之内，然后判断插入的位置是否是队尾，如果是，添加到队尾；否则执行 linkBefore() 方法。

在执行 linkBefore() 方法之前，会调用 node() 方法查找指定位置上的元素，这一步是需要遍历 LinkedList 的。如果插入的位置靠前半截，就从队头开始往后找；否则从队尾往前找。也就是说，如果插入的位置越靠近 LinkedList 的中间位置，遍历所花费的时间就越多。

找到指定位置上的元素（succ）之后，就开始执行 linkBefore() 方法了，先将 succ 的前一个节点（prev）存放到临时变量 pred 中，然后生成新的 Node 节点（newNode），并将 succ 的前一个节点变更为 newNode，如果 pred 为 null，说明插入的是队头，所以 first 为新节点；否则将 pred 的后一个节点变更为 newNode。
在这里插入图片描述

两者对比

当两者的起始长度是一样的情况下：

  • 如果是从集合的头部新增元素，ArrayList 花费的时间要比 LinkedList 多，因为需要对头部以后的元素进行复制；
  • 如果是从集合的中间位置新增元素，ArrayList 花费的时间要比 LinkedList 少，因为 LinkedList 需要遍历；
  • 如果是从集合的尾部新增元素，ArrayList 花费的时间要比 LinkedList 少，因为数组是一段连续的内存空间，也不需要复制数组；而链表需要创建新的对象，前后引用也要重新排序。

这样来看，ArrayList 在添加元素时如果不涉及到扩容，性能在两种情况下（中间位置新增元素、尾部新增元素）比 LinkedList 好很多，只有头部新增元素的时候比 LinkedList 差，因为数组要复制。

当然，如果涉及到数组扩容的话，ArrayList 的性能就没那么可观了，因为扩容的时候也要复制数组。

03、删除元素的速度？

ArrayList 删除

ArrayList 删除元素的时候有两种方式：一种是直接删除元素，需要先遍历数组，找到元素对应的索引；一种是按照索引删除元素。

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;
}


public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

由此可见，remove(Object o) 方法里面调用的是 fastRemove(int index) 方法：

private void fastRemove(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
}

只要删除的不是最后一个元素，就都需要数组重组，并且删除的元素位置越靠前，代价就越大。

LinkedList 删除

LinkedList 删除元素的时候有四种方法，可以扒一下前面的源码查看。

两者对比

  • 从集合头部删除元素时，ArrayList 花费的时间比 LinkedList 多；
  • 从集合中间位置删除元素时，ArrayList 花费的时间比 LinkedList 少；
  • 从尾部删除元素时，ArrayList 花费的时间比 LinkedList 少。

04、遍历元素的速度？

ArrayList 遍历

遍历 ArrayList 找到某个元素的话，通常有两种方式：一种是根据索引找元素；一种是根据元素找索引。

get(int index)，根据索引找元素。因为 ArrayList 是由数组实现的，所以根据索引找元素非常的快，一步到位。

indexOf(Object o)，根据元素找索引。需要遍历整个数组，从头到尾依次找。

LinkedList 遍历

遍历 LinkedList 找到某个元素的话，通常也有两种形式：一种是找到指定位置上的元素；一种是找元素所在的位置。

get(int)，找指定位置上的元素：

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

既然需要调用 node(int index) 方法，就意味着需要前后半段遍历了。

indexOf(Object o)，找元素所在的位置。需要遍历整个链表，和 ArrayList 的 indexOf() 类似。

那在我们对集合遍历的时候，通常有两种做法，一种是使用 for 循环，一种是使用迭代器（Iterator）。

如果使用的是 for 循环，可想而知 LinkedList 在 get 的时候性能会非常差，因为每一次外层的 for 循环，都要执行一次 node(int index) 方法进行前后半段的遍历。

迭代器只会调用一次 node(int index) 方法，在执行 list.iterator() 的时候：先调用 AbstractSequentialList 类的 iterator() 方法，再调用 AbstractList 类的 listIterator() 方法，再调用 LinkedList 类的 listIterator(int) 方法，最后返回的是 LinkedList 类的内部私有类 ListItr 对象。

执行 ListItr 的构造方法时调用了一次 node(int index) 方法，返回第一个节点。在此之后，迭代器就执行 hasNext() 判断有没有下一个，执行 next() 方法下一个节点。

由此，可以得出这样的结论：遍历 LinkedList 的时候，千万不要使用 for 循环，要使用迭代器。

两者对比

for 循环遍历的时候，ArrayList 花费时间远小于 LinkedList；迭代器遍历的时候，两者性能差不多。

05、区别汇总

  • 是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
  • 底层数据结构： ArrayList 底层使用的是 Object 数组；LinkedList 底层使用的是双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环）
  • 插入和删除是否受元素位置的影响：
    • ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。
    • LinkedList 采用链表存储，所以，如果是在头尾插入或者删除元素不受元素位置的影响（add(E e)、addFirst(E e)、addLast(E e)、removeFirst() 、 removeLast()），时间复杂度为 O(1)，如果是要在指定位置 i 插入和删除元素的话（add(int index, E element)，remove(Object o)）， 时间复杂度为 O(n) ，因为需要先移动到指定位置再插入。
  • 是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
  • 内存空间占用： ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

我们在项目中一般是不会使用到 LinkedList 的，需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替，并且性能通常会更好。

另外，不要下意识地认为 LinkedList 作为链表就最适合元素增删的场景，它也仅仅在头尾插入或者删除元素的时候时间复杂度近似 O(1)，其他情况元素的时间复杂度都是 O(n)。

5.5 Java 中的 Iterator 和 Iterable 有什么区别？

在 Java 中，对 List 进行遍历主要有三种方式：

  1. for 循环

    for (int i = 0; i < list.size(); i++) {
    System.out.print(list.get(i) + "，");
}

  2. 迭代器

    Iterator it = list.iterator();
while (it.hasNext()) {
    System.out.print(it.next() + "，");
}

  3. for-each

    for (String str : list) {
    System.out.print(str + "，");
}

第三种看似是 for-each，其实背后也是 Iterator，查看反编译后的代码：

Iterator var2 = list.iterator();

while(var2.hasNext()) {
    String s = (String)var2.next();
    System.out.println(s);
}

由此可见，for-each 只不过是个语法糖，让我们在遍历 List 的时候代码更简洁明了了而已。

查看 ArrayList 或者 LinkedList 的继承派生关系：
JavaSE进阶之（五）Collection 子接口之 List-小白菜博客
我们会发现，无论是 ArrayList 还是 LinkedList，最终继承的接口是 Iterable，而并没有找到 Iterator。也就是说，List 的关系图谱中并没有直接使用 Iterator，而是使用 Iterable 做了过渡。

Iterable 是遍历集合的接口，提供了用于遍历集合的 iterable 方法，里面定义了用于 for-each 元素的具体逻辑，并且返回一个 T 类型的 Iterator 迭代器对象。扒一下 Iterable 的源码：

public interface Iterable<T> {
    /**
     * Returns an iterator over elements of type {@code T}.
     *
     * @return an Iterator.
     */
    Iterator<T> iterator();
}

JDK 1.8 时，Iterable 接口中新增了 forEach() 方法：

default void forEach(Consumer<? super T> action) {
    Objects.requireNonNull(action);
    for (T t : this) {
        action.accept(t);
    }
}

它对 Iterable 的每个元素执行给定的操作，具体指定的操作需要自己写 通过 accept() 方法回调出来：

List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));
list.forEach(integer -> System.out.println(integer));

换种更容易理解的方式来表达：

List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));
// 遍历时传入一个 Consumer 接口作为参数，重写 accept() 方法对 list 集合进行消费
list.forEach(new Consumer<Integer>() {
    @Override
    public void accept(Integer integer) {
    	// 消费方式：直接输出 int 值
        System.out.println(integer); // 1 2 3
    }
});

Iterator 是个迭代器接口，迭代器是一个超级接口，是可以遍历集合的对象。为各种容器提供了公共的操作接口，隔离对容器的遍历操作和底层实现，从而解耦。JDK 1.2 的时候就有了，用来改进 Enumeration：

  • 允许删除元素（增加了 remove 方法）
  • 优化了方法名（Enumeration 中是 hasMoreElements 和 nextElement，不简洁）
    在这里插入图片描述

Iterator 用来遍历集合对象执行的具体操作，扒一下 Iterator 接口的源码：

public interface Iterator<E> {
  	// 判断集合中是否存在下一个对象
    boolean hasNext();
	// 返回集合中的下一个对象，并将访问指针移动一位
    E next();
	// 删除集合中调用 next() 方法返回的对象
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
    
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

回头再来看一下第二种遍历 List 的方式：

Iterator it = list.iterator();
while (it.hasNext()) {
    System.out.print(it.next() + "，");
}

就拿 ArrayList 来说，它重写了 Iterable 接口的 iterator 方法：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
	public Iterator<E> iterator() {
	    return new Itr();
	}
}

返回的对象是一个 Itr 内部类，这个内部类实现了 Iterator 接口，并且按照自己的方式重写了 hasNext()、next()、remove() 等方法：

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    Itr() {}

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

这样就会让人很迷惑：为什么不直接将 Iterator 中的核心方法 hasNext()、next() 方法放到 Iterable 接口中呢？就像下面这样使用不是更简单？

Iterable it = list.iterator();
while (it.hasNext()) {
}

在没有看下文之前，我也很懵逼。

从英文单词的后缀语法上来看，Iterable 是个形容词，表示这个 List 是支持迭代的；而 Iterator 是个名词，表示这个 List 是如何实现迭代的。

支持迭代和具体怎么实现迭代显然不能混在一起使用，就像我们平时开发一样，每个模块都要保持独立性，各司其职。

如果我们强制性的把 Iterable 和 Iterator 合并了，for-each 这种遍历方式就不知道该怎么办了。

原则上，一个 List 只要实现了 Iterable 接口，那么它就可以使用 for-each 这种方式来遍历，具体该怎么实现还是要看它自己是怎么实现 Iterator 接口的。

Map 就没有办法直接使用 for-each，因为 Map 没有实现 Iterable 接口，只有通过 map.entrySet()、map.keySet()、map.values() 这种返回一个 Collection 的方式才能使用 for-each。

如果我们仔细研究 LinkedList 的源码就会发现，LinkedList 并没有直接重写 Iterable 接口的 iterator 方法，而是由它的父类 AbstractSequentialList 来完成的：

public abstract class AbstractSequentialList<E> extends AbstractList<E> {
	public Iterator<E> iterator() {
	    return listIterator();
	}
}

而 LinkedList 重写了 listIterator() 方法：

public ListIterator<E> listIterator(int index) {
	// 校验索引
    checkPositionIndex(index);
    // 返回内部类对象
    return new ListItr(index);
}

这里有一个新的迭代器 ListIterator，它继承了 Iterator 接口，在遍历 List 时可以从任意下标开始遍历，而且支持双向遍历：

public interface ListIterator<E> extends Iterator<E> {
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int previousIndex();
    void remove();
    void set(E e);
    void add(E e);
}

我们都知道，集合（Collection）不仅有 List，还有 Map 和 Set，那 Iterator 不仅支持 List，还支持 Set，但 ListIterator 就只支持 List。

那为什么不直接让 List 实现 Iterator 接口，而是要用内部类来实现呢？

这是因为有些 List 可能会有多种遍历方式，比如说 LinkedList，除了支持正序的遍历方式，还支持 DescendingIterator() 逆序的遍历方式：

private class DescendingIterator implements Iterator<E> {
    private final ListItr itr = new ListItr(size());
    public boolean hasNext() {
        return itr.hasPrevious();
    }
    public E next() {
        return itr.previous();
    }
    public void remove() {
        itr.remove();
    }
}

可以看到，DescendingIterator 刚好利用了 ListIterator 向前遍历的方式。我们一般可以这样来使用：

Iterator it = list.descendingIterator();
while (it.hasNext()) {
}

5.5 为什么不要在 foreach 里执行删除操作？

首先，先来解释一下 fail-fast ：快速失败系统，通常设计用于停止有缺陷的过程，这是一种理念，在进行系统设计时优先考虑异常情况，一旦发生异常，直接停止并上报。举个非常简单的例子：

public int test (int a, int b){
    if (a == 0) {
        throw new RuntimeException("被除数不能为0");    //这里就是fail-fast的体现
    }
    return a / b;
}

也就是说，一旦发现除数是 0，那么直接抛出异常，并明确提示异常原因，这就是 fail-fast 的应用。这样做一方面是为了避免执行接下来复杂的代码，另一方面可以根据错误原因进行针对性的处理。

通常说的 Java 中的 fail-fast 机制，默认指的是 Java 集合中的一种错误检测机制，但其实并不是 Java 集合框架特有的机制，当多个线程对集合进行结构性的改变时，有可能会出发 fail-fast 机制，这个时候会抛出 ConcurrentModificationException 异常。看下面一段代码：

ArrayList<String> arrayList = new ArrayList<String>();
arrayList.add("张三");
arrayList.add("李四");
arrayList.add("王五");

for (String s : arrayList) {
    if ("王五".equals(s)) {
        arrayList.remove(s);
    }
}

这段代码的含义就是遍历集合并删除 “王五” 这个值，但是运行起来就报错：
JavaSE进阶之（五）Collection 子接口之 List-小白菜博客
查看错误信息可以得知，在执行 remove() 方法的时候执行了 checkForComodification() 方法，该方法在执行时因为 modCount 与 expectedModCount 两值不相等，所以抛出了异常。

但是在上面我们扒过源码， checkForComodification() 方法是在迭代器的 next() 方法中调用的，为什么 foreach 循环中也会执行呢？

我们都知道，foreach 本质上是个语法糖，底层是通过迭代器 Iterator 配合 while 循环使用的，也就是说，foreach 循环是通过迭代器实现集合的遍历的。

Iterator 接口有三个方法：

  1. boolean hasNext()：询问有没有下一个元素。
  2. E next()：移动到下一个元素，并返回该位置上的元素。
  3. default void remove()：删除集合元素。

ArrayList 中使用迭代器来实现集合的遍历：

ArrayList<String> arrayList = new ArrayList<String>();
arrayList.add("张三");
arrayList.add("李四");
arrayList.add("王五");

// 获取迭代器
Iterator<String> iterator = arrayList.iterator();
// 遍历集合
while (iterator.hasNext()) {
    String s = iterator.next();
    // 一、并发异常
    if (s.equals("王五")) {
        arrayList.remove("王五");
    }

    // 二、并发异常的特殊情况
    if (s.equals("李四")) {
        arrayList.remove("李四");
    }
	
	// 调用迭代器的默认 remove() 方法
    if (s.equals("张三")) {
        iterator.remove();
    }
}

以上例为基础，扒一下 iterator()方法的源码：

public Iterator<E> iterator() {
	// 创建了一个对象
    return new Itr();
}

在 ArrayList 内部使用了内部类——迭代器的源码：

private class Itr implements Iterator<E> {
	// 初始化成员变量
	// 光标，默认值为 0
    int cursor;       // index of next element to return
    // 记录 -1
    int lastRet = -1; // index of last element returned; -1 if no such
    // 将集合实际修改的次数赋值给预期修改的次数
    // 获取迭代器的时候 expectedModCount 的值为 3（张三、李四、王五）
    int expectedModCount = modCount;

    Itr() {}

	// 判断集合是否有元素
    public boolean hasNext() {
    	// 光标是否不等于集合的size
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
    	// 校验预期修改集合次数和实际修改集合次数是否相同
        checkForComodification();
        // 光标赋值给 i，初始值为0
        int i = cursor;
        // 判断，如果大于集合的size就说明没有元素了
        if (i >= size)
            throw new NoSuchElementException();
        // 把集合 存储数据数组的地址赋值给该方法的局部变量
        Object[] elementData = ArrayList.this.elementData;
        // 判断，如果条件满足就会产生并发修改异常
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        // 光标自增
        cursor = i + 1;
        // 从数组中取出元素并返回
        return (E) elementData[lastRet = i];
    }

	// 校验预期修改集合次数和实际修改集合次数是否一样
	final void checkForComodification() {
         if (modCount != expectedModCount)
         	 // 如果不一样，就会产生并发修改异常
             throw new ConcurrentModificationException();
     }
}

01、 并发修改异常产生的原因

在 new Itr() 的时候 expectedModCount 被赋值为 modCount，modCount 是 List 的一个成员变量，表示集合被修改的次数。list 在此之前执行了 3 次 add() 方法：

  1. add() 方法调用 ensureCapacityInternal() 方法；
  2. ensureCapacityInternal() 方法调用 ensureExplicitCapacity() 方法；
  3. ensureExplicitCapacity() 方法中会进行 modCount++。

所以在经过三次添加后，expectedModCount = 3。

执行第三次循环时，发现 “王五” 等于 s，于是就执行 list.remove(s) 方法：

  1. remove() 方法调用 fastRemove() 方法；
  2. fastRemove() 方法中会执行 modCount++。
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;
}

private void fastRemove(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
}

此时，modCount = 4，也就是说预期修改次数 exceptedModCount = 3，实际修改次数 modCount = 4。调用删除方法进行删除后 size=2 。调用 iterator.hasNext() 继续下一次循环，此时的光标 cursor=3，而 size=2，调用 hasNext() 方法后返回 true，进入循环。接着调用 next() 方法，此方法中首先会校验预期修改集合次数和实际修改集合次数是否相同，显然是不同的，所以就会抛出并发异常。

结论：

  1. 集合每次调用add()方法的时候，实际修改次数变量的值 modCount 都会自增一次；
  2. 在获取迭代器的时候，集合只会执行一次将实际修改集合的次数赋值给预期修改集合的次数；
  3. 集合在删除元素的时候也会针对实际修改次数的变量进行自增的操作。

其实在阿里巴巴的 Java 开发手册里也提到了，不要在 for-each 循环里进行元素的 remove/add 操作。remove 元素请使用 Iterator 方式。
JavaSE进阶之（五）Collection 子接口之 List-小白菜博客
原因其实就是上面分析的这些，出于 fail-fast 保护机制，可以通过 for-each 循环删除集合的元素的方式来验证这种保护机制。

那也就是说，for-each 本质上是一种语法糖，遍历集合时很方便，但并不适合拿来操作集合中的元素（增删）。

02、并发修改异常的特殊情况

当循环到 “李四” 时，调用 remove() 方法。在 fastRemove() 方法中首先进行了 modCount 自增1，也就是说预期修改次数 exceptedModCount = 3，实际修改次数 modCount = 4。调用删除方法进行删除后 size=2 。调用 iterator.hasNext() 继续下一次循环，此时的光标 cursor=2，而 size=2，调用 hasNext() 方法后返回 false，终止循环。所以不会接着调用 next() 方法，也不会去校验预期修改集合次数和实际修改集合次数是否相同。

当要删除的元素在集合的倒数第二个位置时，不会产生并发修改异常。

注意：
但是，在 foreach 循环中无论删除的元素在第几个位置都会抛出并发修改异常。

03、如何正确地删除元素？

1. remove() 后 break

List<String> list = new ArrayList<>();
list.add("张三");
list.add("李四");
list.add("王五");

for (String str : list) {
	if ("张三".equals(str)) {
		list.remove(str);
		break;
	}
}

break 后循环就不再遍历了，意味着 Iterator 的 next() 方法不会再执行了，也就意味着 checkForComodification() 方法不会再执行了，所以异常也就不会抛出了。

但是，当 List 中有重复元素要删除的时候，break 就不合适了。

2. 传统 for 循环

List<String> list = new ArrayList<>();
list.add("张三");
list.add("李四");
list.add("王五");

for (int i = 0, n = list.size(); i < n; i++) {
	String str = list.get(i);
	if ("张三".equals(str)) {
		list.remove(str);
	}
}

for 循环虽然可以避开 fail-fast 保护机制，也就说 remove 元素后不再抛出异常；但是，这段程序在原则上是有问题的。为什么呢？

第一次循环的时候，i 为 0，list.size() 为 3，当执行完 remove 方法后，i 为 1，list.size() 却变成了 2，因为 list 的大小在 remove 后发生了变化，也就意味着 “李四” 这个元素被跳过了没有删除。

remove 之前 list.get(1) 为 “李四”；但 remove 之后 list.get(1) 变成了 “王五”，而 list.get(0) 变成了“李四”。这就导致 “李四” 这个元素没有被删除。

3. 迭代器中的 remove() 方法

List<String> list = new ArrayList<>();
list.add("张三");
list.add("李四");
list.add("王五");

Iterator<String> itr = list.iterator();

while (itr.hasNext()) {
	String str = itr.next();
	if ("王五".equals(str)) {
		itr.remove();
	}
}

为什么使用 Iterator 的 remove() 方法就可以避开 fail-fast 保护机制呢？扒一下 remove() 的源码：

// 迭代器自带的方法
public void remove() {
    if (lastRet < 0)
        throw new IllegalStateException();
    // 校验是否发生并发修改异常
    checkForComodification();

    try {
    	// 调用 ArrayList 的 remove(int index) 方法
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        // 敲重点!!!
        // 把实际修改集合次数赋值给预期修改次数
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

使用迭代器调用 remove() 方法删除元素，其实底层真正还是调用集合自己的删除方法来删除元素。

在调用 remove() 方法删除完后，会每次都给预期修改次数的变量重新赋值：expectedModCount = modCount，保证了 expectedModCount 与 modCount 的同步。