ArrayList源码（二）：扩容和移位、删除元素详解

Java基础

发布时间: 2022-04-07

文章字数: 1.4k

阅读时长: 5 分

关于ArrayList的文章有两篇，前一篇写了ArrayList的数据结构、扩容机制、源码分析等，这篇来看一下ArrayList的一些操作细节。

1. 删除元素操作

1.1 通过foreach删除

List<String> list = new ArrayList<>();
        list.add("1");
        list.add("2");
        list.add("3");
        for (String element : list) {
            System.out.println(element);
            list.remove(element);//删除操作
        }

使用foreach遍历数组，其实底层使用的Iterator，在Iterator创建的时候，维护了一个全局变量expectedModCount，将ArrayList的modCount赋值给expectedModCount。当list发生增、删、改的时候modCount会做递增，但是expectedModCount不会变。

Iterator在执行next方法的时候获取检测expectedModCount和modCount是否相等，当不相等的时候会抛出ConcurrentModificationException异常。由此可见，上面的代码在执行的过程中或出现异常的问题。

解释源码如下：

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; //初始化expectedModCount，与modCount等
    //……
}

public E next() {
    checkForComodification();// 检查expectedModCount、modCount
    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];
}
// 检查expectedModCount、modCount
final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

1.2 通过for循环删除

List<String> list = new ArrayList<>();
list.add("1");
list.add("2");
list.add("3");
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
    list.remove(i);
}

此方式循环删除，不会出现异常问题，因为使用的是ArrayList本身的API，不会触发Iterator的检查机制。但是会出现数据遍历不全的问题。我们都知道在ArrayList中删除元素后，被删除的元素后面的元素会向前移动一位，这个时候就会导致被删除元素的下一个元素移动到删除元素的位置，出现遗漏遍历的问题，具体如下：

在这里插入图片描述

当遍历角标为0的元素后，删除角标为0的元素，此时原来的数组就会变成第二种情况，所有元素向前移动一位；
当循环循环继续，此时遍历的角标为1的元素，取到的值不是2，而是3，也就是说2漏掉了，没有遍历到。

1.3 正确的ArrayList增删改姿势

通过上面的两种删除操作比较，都是存在很大的问题的，在实际开发都不能使用，但是此时就需要对ArrayList遍历，并进行增删改操作怎么办呢？那就通过Iterator或者ListIterator来实现。

List<String> list = new ArrayList<>();
list.add("1");
list.add("2");
list.add("2");
list.add("3");
System.out.println("删除前的List:" + list);
ListIterator<String> listIterator = list.listIterator();
// 或者直接使用lambda表达式代替整个while循环：list.removeIf("2"::equals); -- 一行代码搞定
while (listIterator.hasNext()) {
    String element = listIterator.next();
    if ("2".equals(element)) { //删除list集合值为“2”的元素
        listIterator.remove();
    }
}
System.out.println("删除后的List:" + list);

为什么这样就可以了呢？不会出现ConcurrentModificationException异常吗？下面看一下源码解释！

// 这个对应的是Iterator内部的add方法
public void add(E e) {
    checkForComodification(); // 检查expectedModCount、modCount
    try {
        int i = cursor;
        ArrayList.this.add(i, e); // 添加元素
        cursor = i + 1;
        lastRet = -1;
        expectedModCount = modCount; // 重新给expectedModCount赋值
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}
// 这个对应的是Iterator内部的remove方法
public void remove() {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();// 检查expectedModCount、modCount
    try {
        SubList.this.remove(lastRet);// 删除元素
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = ArrayList.this.modCount;//重新给expectedModCount赋值
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

从上面的代码可以看出来，在通过Iterator（或者ListIterator）增、删方法操作后会重新维护expectedModCount的值，保证与ArrayList.this.modCount相同，再下次进行checkForComodification()方法时，自然不会出现两者值不同的问题，就不会出现ConcurrentModificationException异常。

2. ArrayList扩容和移位的区别

ArrayList扩容是对动态数组做增长操作，而移位是在原有的数组长度不变的情况下，移动部分元素在数组中的位置。举个例子:

开会的时候，有一排5个座位，此时坐了4个人，挨着坐的，后来来了一个领导，就需要将中间位置让给领导，那么就需要其中两位移动一下位置，坐变边上的两个座位，领导插入中间。这就是移位，本身座位个数是没有变化的。
一个盒子只能装下4个苹果，现在需要再放一个苹果，那就要重新寻找一个大盒子，把之前小盒子里面的苹果以及增加的这个苹果一起放到大盒子中。这个就是扩容了，存储苹果的盒子及位置发生了变化。

细心的同学在看ArrayList源码的时候可以看到，其内部频繁使用了两个方法System.arraycopy()和Arrays.copyOf()。