在ArrayList的循环中删除元素，会不会出现问题？

如下的五种删除方式可以动手试试并看看结果

import java.util.ArrayList;
import java.util.Iterator;

public class ArrayListTest {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<String>();
        list.add("aa");
        list.add("bb");
        list.add("bb");
        list.add("aa");
        list.add("cc");
        // 删除元素 bb
        remove1(list, "bb");
        for (String str : list) {
            System.out.println(str);
        }
    }
    public static void remove1(ArrayList<String> list, String elem) {
        // 方法一：普通for循环正序删除，删除过程中元素向左移动，不能删除重复的元素
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).equals(elem)) {
                list.remove(list.get(i));
            }
        }
    }


    public static void remove2(ArrayList<String> list, String elem) {
        // 方法二：普通for循环倒序删除，删除过程中元素向左移动，可以删除重复的元素
        for (int i = list.size() - 1; i >= 0; i--) {
            if (list.get(i).equals(elem)) {
                list.remove(list.get(i));
            }
        }
    }

    public static void remove3(ArrayList<String> list, String elem) {
        // 方法三：增强for循环删除，使用ArrayList的remove()方法删除，产生并发修改异常 ConcurrentModificationException
        for (String str : list) {
            if (str.equals(elem)) {
                list.remove(str);
            }
        }
    }

    public static void remove4(ArrayList<String> list, String elem) {
        // 方法四：迭代器，使用ArrayList的remove()方法删除，产生并发修改异常 ConcurrentModificationException
        Iterator iterator = list.iterator();
        while (iterator.hasNext()) {
            if(iterator.next().equals(elem)) {
                list.remove(iterator.next());
            }
        }

    }

    public static void remove5(ArrayList<String> list, String elem) {
        // 方法五：迭代器，使用迭代器的remove()方法删除，可以删除重复的元素，但不推荐
        Iterator iterator = list.iterator();
        while (iterator.hasNext()) {
            if(iterator.next().equals(elem)) {
                iterator.remove();
            }
        }

    }
}

ArrayList的Remove方法的源码如下

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

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
}

可以看到这个 remove() 方法被重载了，一种是根据下标删除，一种是根据元素删除，这也都很好理解。

根据下标删除的 remove() 方法，大致的步骤如下：

• 1、检查有没有下标越界，就是检查一下当前的下标有没有大于等于数组的长度
• 2、列表被修改（add和remove操作）的次数加1
• 3、保存要删除的值
• 4、计算移动的元素数量
• 5、删除位置后面的元素向左移动，这里是用数组拷贝实现的
• 6、将最后一个位置引用设为 null，使垃圾回收器回收这块内存
• 7、返回删除元素的值

根据元素删除的 remove() 方法，大致的步骤如下：

• 1、元素值分为null和非null值

• 2、循环遍历判等

• 3、调用 fastRemove(i) 函数

  • 3.1、修改次数加1

  • 3.2、计算移动的元素数量

  • 3.3、数组拷贝实现元素向左移动

  • 3.4、将最后一个位置引用设为 null

  • 3.5、返回 fase

• 4、返回 true

我们重点关注的是删除过程，学过数据结构的小伙伴可能手写过这样的删除，下面我画个图来让大家更清楚的看到整个删除的过程。以删除 “bb” 为例，当指到下标为 1 的元素时，发现是 "bb"，此处元素应该被删除，根据上面的删除步骤可知，删除位置后面的元素要向前移动，移动之后 “bb” 后面的 “bb” 元素下标为1，后面的元素下标也依次减1，这是在 i = 1 时循环的操作。在下一次循环中 i = 2，第二个 “bb” 元素就被遗漏了，所以这种删除方法在删除连续重复元素时会有问题。但是如果我们使 i 递减循环，也即是方法二的倒序循环，这个问题就不存在了，正序删除和倒序删除如下图所示。

直接进入ArrayList的源代码可以发现，在1.5的版本后，ArrayList中创建了一个内部迭代器Itr，并实现了Iterator接口，而For-Each遍历正是基于这个迭代器的hasNext()和next()方法来实现的；

先看一下这个内部迭代器：

/**
     * An optimized version of AbstractList.Itr
     */
    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;

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

        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }

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

这里有两个变量需要注意：
一个是modCount：这个外部的变量，也就是ArrayList下的变量：

/**
     * The number of times this list has been <i>structurally modified</i>.
     * Structural modifications are those that change the size of the
     * list, or otherwise perturb it in such a fashion that iterations in
     * progress may yield incorrect results.
     *
    ….
     */
    protected transient int modCount = 0;

只贴前面一部分注释，注释说这个变量来记录ArrayList集合的修改次数，也说明了可能会和迭代器内部的期望值不一致；

另外一个是Itr的变量expectedModCount;
能过上面的代码可以看到在Itr创建时默认定义了 int expectedModCount = modCount;

我们先只看remove的操作:

我们进入到ArrayList下的remove方法，注意这里并没有进入内部迭代器Itr的remove()方法【这里是产生异常的关键点】

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

很显然，这里应该正常的走到了fastRemove()方法中：

   /*
     * Private remove method that skips bounds checking and does not
     * return the value removed.
     */
    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
    }

这里可以看到在fastRemove()方法中通过modCount++ 自增了一次，而此时并没有改变内部迭代器Itr中的expectedModCount 的值；

我们再往下走，此会再迭代到下一个元素；
先会通过hasNext(){return cursor != size;}来判断是否还有元素，很显然，若删除前面的元素，此处一定会为true（注意：若之前删除的是倒数第二个元素，此处的cursor就是最后一个索引值size()-1,而由于已成功删除一个元素，此处的siz也是原size()-1,两者相等，此处会返回false）
而在调用next()方面来获取下一个元素时，可以看到在next()方法中先调用了checkForComodification()方法：

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

很显然，此处的modCount已经比expectedModCount大1了，肯定不一样，if条件成立，抛出一个ConcurrentModificationException异常。

致此，我们大概理清了为什么在foreach快速遍历中删除元素会崩溃的原因。

总结一下：
1）在使用For-Each快速遍历时，ArrayList内部创建了一个内部迭代器iterator，使用的是hasNext和next()方法来判断和取下一个元素。
2）ArrayList里还保存了一个变量modCount，用来记录List修改的次数，而iterator保存了一个expectedModCount来表示期望的修改次数，在每个操作前都会判断两者值是否一样，不一样则会抛出异常；
3）在foreach循环中调用remove()方法后，会走到fastRemove()方法，该方法不是iterator中的方法，而是ArrayList中的方法，在该方法中modCount++; 而iterator中的expectedModCount并没有改变；
4）再次遍历时，会先调用内部类iteator中的hasNext(),再调用next(),在调用next()方法时，会对modCount和expectedModCount进行比较，此时两者不一致，就抛出了ConcurrentModificationException异常。

而为什么只有在删除倒数第二个元素时程序没有报错呢？

因为在删除倒数第二个位置的元素后，开始遍历最后一个元素时，先会走到内部类iterator的hasNext()方法时，里面返回的是 return cursor != size; 此时cursor是最后一个索引值，即原size()-1,而由于已经删除了一个元素，该方法内的size也是原size()-1,故 return cursor != size；会返回false,直接退出for循环，程序便不会报错。

最后，通过源代码的判断，要在循环中删除元素，最好的方式还是直接拿到ArrayList对象下的迭代器list.iterator()，通过源码可以看到，该方法也就是直接把内部的迭代器返回出来

  public Iterator<E> iterator() {
        return new Itr();
    }

而该迭代器正是在For-Each快速遍历中使用的迭代器Itr。

作者：南山伐木
链接：https://www.jianshu.com/p/58c4af5b97ff
来源：简书
简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。