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

在 ArrayList 的循环中删除元素，会不会出现问题？我开始觉得应该会有什么问题吧，但是不知道问题会在哪里。在经历了一番测试和查阅之后，发现这个“小”问题并不简单！

不在循环中的删除，是没有问题的，否则这个方法也没有存在的必要了嘛，我们这里探讨的是在循环中的删除，而对 ArrayList 的循环方法也是有多种的，这里定义一个类方法 remove()，里面有五种删除的实现方法，有的方法运行时会报错，有的是能运行但不能删除完全，读者也可以一一测试。

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        remove(list, "bb");        for (String str : list) {            System.out.println(str);        }    }    public static void remove(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));//            }//        }        // 方法二：普通for循环倒序删除，删除过程中元素向左移动，可以删除重复的元素//        for (int i = list.size() - 1; i >= 0; i--) {//            if (list.get(i).equals(elem)) {//                list.remove(list.get(i));//            }//        }        // 方法三：加强for循环删除，用ArrayList的remove()方法删除，产生并发修改异常 ConcurrentModificationException//        for (String str : list) {//            if (str.equals(elem)) {//                list.remove(str);//            }//        }        // 方法四：迭代器，用ArrayList的remove()方法删除，产生并发修改异常 ConcurrentModificationException//        Iterator iterator = list.iterator();//        while (iterator.hasNext()) {//            if(iterator.next().equals(elem)) {//                list.remove(iterator.next());//            }//        }        // 方法五：迭代器，用迭代器的remove()方法删除，可以删除重复的元素，但不推荐//        Iterator iterator = list.iterator();//        while (iterator.hasNext()) {//            if(iterator.next().equals(elem)) {//                iterator.remove();//            }//        }    }}

这里我测试了五种不同的删除方法，一种是普通的 for 循环，一种是加强的 foreach 循环，还有一种是用迭代器循环，一共这三种循环方式。也欢迎你留言和我们探讨哦！

上面这几种删除方式呢，在删除 list 中单个的元素，也即是没有重复的元素，如 “cc”。在方法三和方法四中都会产生并发修改异常 ConcurrentModificationException，这两个删除方式中都使用到了 ArrayList 中的 remove() 方法（快去上面看看代码吧）。而在删除 list 中重复的元素时，会有这么两种情况，一种是这两个重复元素是紧挨着的，如 “bb”，另一种是这两个重复元素没有紧挨着，如 “aa”。删除这种元素时，方法一在删除重复但不连续的元素时是正常的，但在删除重复且连续的元素时，会出现删除不完全的问题，这种删除方式也是使用到了 ArrayList 中的 remove() 方法。而另外两种方法都是可以正常删除的，但是不推荐第五种方式，这个后面再说。

经过对运行结果的分析，发现问题都指向了 ArrayList 中的 remove() 方法，（感觉有种侦探办案的味道，可能是代码写多了的错觉吧，txtx…）那么看 ArrayList 源码是最好的选择了，下面是我截取的关键代码（Java1.8）。

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

这里我有个疑问，第一个 remove() 方法中的代码和 fastRemove() 方法中的代码是完全一样的，第一个 remove() 方法完全可以向第二个 remove() 方法一样调使用 fastRemove() 方法嘛，这里代码的确是有些冗余，我又看了 Java10 的源码，这里编码作者已经修改了，而且代码写的很六~，看了半天才看懂大牛的高超的编程技巧，有兴趣的小伙伴可以去看看。

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

删除操作.jpg

既然我们已经搞清不能正常删除的起因，那么再来看看方法五中可以正常删除的起因。方法五中用的是迭代器中的 remove() 方法，通过阅读 ArrayList 的源码可以发现，有两个私有内部类，Itr 和 ListItr，Itr 实现自 Iterator 接口，ListItr 继承 Itr 类和实现自 ListIterator 接口。Itr 类中也有一个 remove() 方法，迭代器实际调使用的也正是这个 remove() 方法，我也截取这个方法的源码。

private class Itr implements Iterator<E>private class ListItr extends Itr implements ListIterator<E> 

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();    }}final void checkForComodification() {    if (modCount != expectedModCount)        throw new ConcurrentModificationException();}

可以看到这个 remove() 方法中调使用了 ArrayList 中的 remove() 方法，那为什么方法四会抛出并发修改异常而这里就没有问题呢？这里注意 expectedModCount 变量和 modCount 变量，modCount 在前面的代码中也见到了，它记录了 list 修改的次数，而前面还有一个 expectedModCount，这个变量的初值和 modCount 相等。在 ArrayList.this.remove(lastRet); 代码前面，还调使用了检查修改次数的方法 checkForComodification()，这个方法里面做的事情很简单，假如 modCount 和 expectedModCount 不相等，那么就抛出 ConcurrentModificationException，而在这个 remove() 方法中存在 “expectedModCount = modCount`，两个变量值在 ArrayList 的 remove() 方法后，进行了同步，所以不会有异常抛出，并且在循环过程中，也不会遗漏连续重复的元素，所以可以正常删除。上面这些代码都是在单线程中执行的，假如换到多线程中，方法五不能保证两个变量修改的一致性，结果具备不确定性，所以不推荐这种方法。而方法一在单线程和多线程中都是可以正常删除的，多线程中测试代码如下，这里我只模拟了三个线程（注：这里我没有使用 Java8 新添加的 Lambda 表达式）：

import java.util.ArrayList;import java.util.Iterator;public class MultiThreadArrayList {    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");        list.add("dd");        list.add("dd");        list.add("cc");        Thread thread1 = new Thread() {            @Override            public void run() {                remove(list,"aa");                try {                    Thread.sleep(1000);                } catch (InterruptedException e) {                    e.printStackTrace();                }            }        };        Thread thread2 = new Thread() {            @Override            public void run() {                remove(list, "bb");                try {                    Thread.sleep(1000);                } catch (InterruptedException e) {                    e.printStackTrace();                }            }        };        Thread thread3 = new Thread() {            @Override            public void run() {                remove(list, "dd");                try {                    Thread.sleep(1000);                } catch (InterruptedException e) {                    e.printStackTrace();                }            }        };        // 使各个线程处于就绪状态        thread1.start();        thread2.start();        thread3.start();        // 等待前面几个线程完成        try {            thread1.join();            thread2.join();        } catch (InterruptedException e) {            e.printStackTrace();        }        for (String str : list) {            System.out.println(str);        }    }    public static void remove(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));            }        }        // 迭代器删除，多线程环境下无法用//        Iterator iterator = list.iterator();//        while (iterator.hasNext()) {//            if(iterator.next().equals(elem)) {//                iterator.remove();//            }//        }    }}

既然 Java 的循环删除有问题，发散一下思维，Python 中的列表删除会不会也有这样的问题呢，我抱着好奇试了试，发现下面的方法一也同样存在不能删除连续重复元素的问题，方法二则是报列表下标越界的异常，测试代码如下，这里我只测试了单线程环境：

list = []list.append("aa")list.append("bb")list.append("bb")list.append("aa")list.append("cc")# 方法一，存在和 Java 相同的删除问题# for str in list:#     if str == "bb":#         list.remove(str)# 方法二，直接报错# for i in range(len(list)):#    if list[i] == "bb":#        list.remove(list[i])for str in list:    print(str)

总结：一道看似很简单的问题，没想到背后却有这么多的知识，真是感觉自己要学的还很多，遇到方法细节的问题，我觉得直接看源码是最好的处理方法，另外我觉得在后面的版本的 JDK 中，可以添加一个在循环中删除连续重复元素的方法，对于用者来说更好少量。

欢迎关注下方的微信公众号哦，另外还有各种学习资料免费分享！

编程心路