ArrayList中的遍历删除

ArrayList 中的遍历删除

在代码编写过程中经常会遇到这样的要求:遍历一个线性表,要求只遍历一遍(时间复杂度\(O(n)\)),删除符合指定条件的元素,且要求空间复杂度 \(O(1)\)。

例如我们有下列数据,要求遍历列表并删除所有偶数。

List<Integer> myList = new ArrayList<>(Arrays.toList(new Integer[]{2, 3, 5, 8, 10, 9}));

代码1:直接遍历列表并删除(错误)

初学者可能会直观地认为,我直接一个for循环遍历删除不就好了吗?但实际上这种做法是错误的。

static void remove1(List<Integer> list) {
    for (int i = 0; i < list.size(); i++) {
        if (list.get(i) % 2 == 0) {
            list.remove(i);
        }
    }
}

使用上面的测试数据,结果为:[3, 5, 7, 10, 9],其中一个偶数 10 并没有被删除。

事实上,当删除列表中元素时,列表的 size() 会改变!当第一个 2 被删除时,此时 list.size() 已经从 6 变成了 5,而 i 只会一直向前跑,因此当 8 被删除时,list.size() 为 4,此时 i 已经变为 5,不再满足 i < list.size() 的循环条件,就会退出循环,后面的元素也不会再被处理。

代码2:控制循环变量的遍历(低效)

第二种做法是,不采用 for 循环,而是采用 while 循环 + 控制循环变量 i 的做法。

static void remove2(List<Integer> list) {
    int i = 0;
    int j;
    while (i < list.size()) {
        if (list.get(i) % 2 == 0) {
            j = i--;
            // 此处存在 i < 0 的可能,所以要及时恢复 i 的位置
            if (i < 0) {
                i = 0;
            }
            list.remove(j); // 注意此处删除的是 j(也就是原来的 i)指向的元素
        } else {
            i++;
        }
    }
}

这里要对循环变量 i 进行控制,当删除一个元素时,i 并不能向前进一个位置而应该向后回退一个位置,从这个回退的位置开始重新向前走,才不至于遗漏本应被遍历到的元素。

代码3:使用迭代器(推荐)

一种更好的写法是使用迭代器,因为迭代器会自动判断列表中的每一个元素是否被遍历过。事实上,迭代器的实现和代码 2 很接近,但是可读性更好。

static void remove3(List<Integer> list) {
    Iterator<Integer> iterator = list.iterator();
    while (iterator.hasNext()) {
        Integer next = iterator.next();
        if (next % 2 == 0) {
            iterator.remove();
        }
    }
}

代码4:使用 removeIf() 方法

Java 中对 ArrayList 类还支持一种 removeIf() 方法,参数传入一个 Predicate 接口的实现对象或一个 lambda 表达式即可。

static void remove4(List<Integer> list) {
    list.removeIf(new Predicate<Integer>() {
        @Override
        public boolean test(Integer i) {
            return i % 2 == 0;
        }
    });
}

或者采用 lambda 表达式,更简洁:

list.removeIf(i -> i % 2 == 0);

以上就是对列表遍历删除的方法总结。如果条件比较简单,可以直接采用 removeIf() 方法,如果条件比较复杂,那么采用迭代器是一种比较好的方法。

上一篇:Iterator 和 for...of 循环


下一篇:集合的遍历的三种方式