在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("aa");
        list.add("bb");
        list.add("cc");
        // 删除元素 aa
        remove(list, "aa");
        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("bb")) {
//                list.remove(list.get(i));
//            }
//        }
        // 方法二:普通for循环倒序删除,删除过程中元素向左移动,可以删除重复的元素
//        for (int i = list.size() - 1; i >= 0; i--) {
//            if (list.get(i).equals("bb")) {
//                list.remove(list.get(i));
//            }
//        }
        // 方法三:增强for循环删除,使用ArrayList的remove()方法删除,产生并发修改异常 ConcurrentModificationException
//        for (String str : list) {
//            if (str.equals("aa")) {
//                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() 方法嘛,这里代码感觉有些冗余,个人理解有限,还请知道的大佬指教。

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

循环中的正序删除.jpg

但是如果我们使 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() 方法后,进行了同步,所以不会有异常抛出,并且在循环过程中,也不会遗漏连续重复的元素,所以可以正常删除。上面这些代码都是在单线程中执行的,如果换到多线程中,方法五不能保证两个变量修改的一致性,结果具有不确定性,所以不推荐这种方法。而方法一在单线程和多线程中都是可以正常删除的,多线程中测试代码如下,这里我只模拟了三个线程:

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")
# 方法一
# 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 中,可以增加一个在循环中删除连续元素的方法嘛,不然这里对于没有发现这个问题的人真是个坑。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏杨熹的专栏

【LEETCODE】模拟面试-39. Combination Sum

和subset区别:规定了子集的sum==target 注意,这里传递的起始位置是i,而不是position+1,but why??? helper(res, ...

2845
来自专栏LanceToBigData

JavaSE(八)之集合概述

前几天其实一直在学习关于linux的内容和kvm虚拟化的知识。今天有时间来回顾一下集合相关的知识,接下来我将带大家一起来回顾一起集合关联的知识。 不要辜负自己花...

1845
来自专栏赵俊的Java专栏

从源码上分析 LinkedList(附图)

1595
来自专栏用户画像

HashSet和HashMap的区别 && HashTable和HashMap的区别

2.Hashtable 中的方法是同步的,而HashMap中的方法在缺省情况下是非同步的。

943
来自专栏kevindroid

leetcode 93. Restore IP Addresses

1904
来自专栏desperate633

LintCode 用递归打印数字题目分析代码

recursion(i) { if i > largest number: return results.add(i) recursion(i + 1)...

661
来自专栏尾尾部落

[LeetCode]Degree of an Array 数组的度 [LeetCode]Degree of an Array 数组的度

链接:https://leetcode.com/problems/degree-of-an-array/description/ 难度:Easy 题目:69...

1122
来自专栏java一日一条

如何用Map对象创建Set对象

Java中的Map和Set有不少相似之处。本文将分享一个把Map类转化成Set类的小技巧。

731
来自专栏java一日一条

集合类操作优化经验总结

在实际的项目开发中会有很多的对象,如何高效、方便地管理对象,成为影响程序性能与可维护性的重要环节。Java 提供了集合框架来解决此类问题,线性表、链表、哈希表等...

832
来自专栏闵开慧

HashMap与HashTable区别

1 HashMap不是线程安全的 hastmap是一个接口 是map接口的子接口,是将键映射到值的对象,其中键和值都是对象,并且不能包含重复键,但可以包含重复...

2686

扫码关注云+社区

领取腾讯云代金券