阿里面试官问我知道哪几种ArrayList的删除姿势？

2021-09-13 03:30:57

引言

前几天有个读者由于看了《ArrayList哪种遍历效率最好，你真的弄明白了吗？》问了个问题普通for循环ArrayList为什么不能删除连续重复的两个元素？其实这个描述是不正确的。正确的应该是普通for循环正序删除，不能删除连续的元素所以就产生了这个文章。
阿里面试官问我知道哪几种ArrayList的删除姿势？

ArrayList删除数据的方式

我们先看下ArrayList总共有几种删除元素的方法吧。

package com.workit.demo.array;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.function.Predicate;

/**

  • @author:
  • @Date: 2020/6/9
  • @Description:
    */

public class ArrayListDelete {

public static void main(String[] args) {

    Predicate<String> predicate = p -> p.equals("a") || p.equals("b");

    // 可以正常删除结果正确
    deleteByIterator(getList(), predicate);

    // 可以正常删除结果正确
    deleteByReverseOrder(getList(), predicate);

    // 可以删除 结果不正确
    deleteByOrder(getList(), predicate);

    // 不能删除 报错java.util.ConcurrentModificationException
    deleteByArrayList(getList(), predicate);

    // 不能删除 报错java.util.ConcurrentModificationException
    deleteByForeach(getList(), predicate);

    //不能删除 报错 java.util.ConcurrentModificationException
    deleteByEnhancedForLoop(getList(), predicate);
    // 正常删除数据        
    deleteAll(getList(), predicate);

}

public static  List<String> getList() {
    List<String> list = new ArrayList<>();
    list.add("a");
    list.add("b");
    list.add("c");
    return list;
}

/**
 * 普通for循环倒序删除
 * 可以正常删除  结果正确
 * @param list
 * @param predicate
 */
public static void deleteByReverseOrder(List<String> list, Predicate<String> predicate) {
    for (int i = list.size() - 1; i >= 0; i--) {
        if (predicate.test(list.get(i))) {
            list.remove(list.get(i));
        }
    }
    System.out.println(Thread.currentThread().getStackTrace()[1].getMethodName()+":"+list.toString());
}

/**
 * 普通for循环正序删除
 *可以删除  结果不正确
 * @param list
 * @param predicate
 */

public static void deleteByOrder(List<String> list, Predicate<String> predicate) {
    for (int i = 0; i < list.size(); i++) {
        if (predicate.test(list.get(i))) {
            list.remove(list.get(i));
        }
    }
    System.out.println(Thread.currentThread().getStackTrace()[1].getMethodName()+":"+list.toString());
}

/**
 * 迭代器循环，使用ArrayList的remove()方法删除
 * 可以删除  结果不正确
 * @param list
 * @param predicate
 */
public static void deleteByArrayList(List<String> list, Predicate<String> predicate) {
    Iterator<String> iterator = list.iterator();
    while (iterator.hasNext()) {
        if (predicate.test(iterator.next())) {
            list.remove(iterator.next());
        }
    }
    System.out.println(Thread.currentThread().getStackTrace()[1].getMethodName()+":"+list.toString());

}

/**
 * 迭代器循环，使用迭代器的remove()方法删除
 * 可以正常删除结果正确
 * @param list
 * @param predicate
 */
public static void deleteByIterator(List<String> list, Predicate<String> predicate) {
    Iterator<String> iterator = list.iterator();
    while (iterator.hasNext()) {
        if (predicate.test(iterator.next())) {
            iterator.remove();
        }
    }
    System.out.println(Thread.currentThread().getStackTrace()[1].getMethodName()+":"+list.toString());

}

/**
 * java8 forEach方法删除
 *不能删除 报错 java.util.ConcurrentModificationException
 * @param list
 * @param predicate
 */
public static void deleteByForeach(List<String> list, Predicate<String> predicate) {
    list.forEach(p -> {
        if (predicate.test(p)) {
            list.remove(p);
        }
    });
    System.out.println(Thread.currentThread().getStackTrace()[1].getMethodName()+":"+list.toString());

}
/**
 * 增强版for循环删除
 *不能删除 报错 java.util.ConcurrentModificationException
 * @param list
 * @param predicate
 */
public static void deleteByEnhancedForLoop(List<String> list, Predicate<String> predicate) {
    for (String string : list) {
        if (predicate.test(string)) {
            list.remove(string);
        }
    }
}

}
/**

 * 调用批量删除方法
 * @param list
 * @param predicate
 */
public static void deleteAll(List<String> list, Predicate<String> predicate) {
    List<String> removeList = new ArrayList<>();
    for (String string : list) {
        if (predicate.test(string)) {
            removeList.add(string);
        }
    }
    list.removeAll(removeList);
    System.out.println(Thread.currentThread().getStackTrace()[1].getMethodName()+":"+list.toString());

}

下面我们来分析下为什么这些方法为什么有的可以正确删除元素，有的不可以。引用大佬们经常说的一句话源码之下无秘密那我们就把源码搞起来吧。

增强版for循环删除 && 迭代器循环使用ArrayList.remove()方法删除

  • 增强版for循环删除（deleteByEnhancedForLoop）、迭代器循环，使用ArrayList的remove()方法删除（deleteByArrayList）这两种姿势都会抛出java.util.ConcurrentModificationException他们本质都是迭代器循环，每次循环都会checkForComodification这个方法检查modCount 和expectedModCount的值。
@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];
    }
     final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }

而List的删除方法每次删除之后modCount都会进行加1操作，expectedModCount值不变还是原来的。

private void fastRemove(int index) {

    modCount++; //modCount`都会进行加1操作
    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
}

所以上面两个方法都会抛出ConcurrentModificationException异常。

java8 forEach方法删除(抛出异常)

  • java8 forEach方法删除（deleteByForeach）为什么也会抛**ConcurrentModificationException异常呢？答案还是在源码里面。
    同上面一样删除一个元素后modCount 进行了加1而expectedModCount 没有变化。

public void forEach(Consumer<? super E> action) {

    Objects.requireNonNull(action);
    final int expectedModCount = modCount;
    @SuppressWarnings("unchecked")
    final E[] elementData = (E[]) this.elementData;
    final int size = this.size;
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        action.accept(elementData[i]);
    }
    if (modCount != expectedModCount) { // 是不是又是这个判断
        throw new ConcurrentModificationException();
    }

正序删除不能删除连续元素的原因

  • 可以删除但是结果不正确的方法for循环正序删除（deleteByOrder）
    先来张图吧，看图更直观。

阿里面试官问我知道哪几种ArrayList的删除姿势？
数组删除元素后每次都需要移动。第一次删除（i=0）后b的下标就为0了，然后第二次(i=1)进行删除的时候是不是就成功的把b给遗漏了。（倒序循环删除就可以避免这种情况）那如果我们非要使用正序循环删除数据那有什么解决办法吗？办法是有的只要在删除后面把i的值进行修正下。代码如下：

for (int i = 0; i < list.size(); i++) {

        if (predicate.test(list.get(i))) {
            list.remove(list.get(i));
            // 新增这个修正i的值
            i--;
        }
    }

是不是又get了一个骚操作。
阿里面试官问我知道哪几种ArrayList的删除姿势？

使用迭代器的remove()方法删除（推荐做法）

迭代器循环，使用迭代器的remove()方法删除（deleteByIterator）这个比较简单我们直接看迭代器的删除
关键代码就一行 expectedModCount = modCount

public void remove() {

        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount; //调用ArrayList的删除方法后多了这么一句话。
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

这种方法也是《阿里开发手册》（需要的可以公众号回复：泰山）推荐的。
阿里面试官问我知道哪几种ArrayList的删除姿势？

总结

上面列举了一系列的删除方法，稍不小心使用不当就踩坑里面了。这么多我也记不住啊？最好的方法就是不要边循环边删除数据。如果非要删除咧？个人建议可以使用批量删除方法（本人屡试不爽）或者迭代器的remove()方法。

结束

  • 由于自己才疏学浅，难免会有纰漏，假如你发现了错误的地方，还望留言给我指出来,我会对其加以修正。
  • 如果你觉得文章还不错，你的转发、分享、赞赏、点赞、留言就是对我最大的鼓励。
  • 感谢您的阅读,十分欢迎并感谢您的关注（微信号是Java金融）
上一篇：阿里面试官：让我说说HashMap的循环？


下一篇：阿里面试，面试官问我代理模式，我给他讲了几个小故事给他整的明明白白