Java ArrayList遍历删除相关

以前面试被问过java.util.ArrayList遍历删除相关的问题。后来的工作中也遇到了一些坑，今天拿出来总结一下。如下：

public static void main(String[] args) {
    List<String> list = new ArrayList<String>();
    list.add("str1");
    list.add("str2");
    list.add("str2");
    list.add("str3");
    list.add("str3");
    list.add("str3");
    //删除所有"str2"元素
    doRemoveStr2(list);
    System.out.println(list);
}

方法一：

public static void doRemoveStr2(ArrayList<String> list) {
       for (int i = 0; i < list.size(); i++) {
           String str = list.get(i);
           if (str.equals("str2")) {
               list.remove(str);
           }
       }
   }

结果：第二个”str2”没有被删掉。

错误原因

首先看下ArrayList源码：

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 void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,numMoved);
        elementData[--size] = null; // Let gc do its work
    }

可以看到，在遍历到第一个”str2”时，符合删除条件，把它从数组中删除，并且把后一个元素，也就是第二个”str2”移动到当前位置，这样，下次循环遍历时就会跳过它，所以无法删除。

解决方法

倒序遍历删除：

public static void doRemoveStr2(ArrayList<String> list) {
        for (int i = list.size() - 1; i >= 0; i--) {
            String s = list.get(i);
            if (s.equals("str2")) {
                list.remove(s);
            }
        }
    }

注

有时为了优化，在遍历之前先把list.size()计算出来保存起来，在这种情况下，list.size()是没有删除之前的大小，最终会报ArrayIndexOutOfBoundsException，注意此坑。

方法二：

使用for-each遍历删除

public static void doRemoveStr2(ArrayList<String> list) {
      for (String s : list) {
          if (s.equals("str2")) {
              list.remove(s);
          }
      }
  }

结果

报出异常：Java.util.ConcurrentModificationException

错误原因

foreach写法实际是对Iterable、hasNext、next方法的简写，问题同样处在上文的fastRemove方法中，可以看到第一行把modCount变量的值加一，但在ArrayList返回的迭代器（该代码在其父类AbstractList中）：

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

这里返回的是AbstractList类内部的迭代器实现private class Itr implements Iterator，看这个类的next方法：

public E next() {
    checkForComodification();
    try {
        E next = get(cursor);
        lastRet = cursor++;
        return next;
    } catch (IndexOutOfBoundsException e) {
        checkForComodification();
        throw new NoSuchElementException();
    }
}

第一行checkForComodification方法：

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

这里会做迭代器内部修改次数检查，因为上面的remove(Object)方法修改了modCount的值，所以才会报出并发修改异常。

正确方法

使用迭代器迭代，（显式或for-each的隐式）不要使用ArrayList的remove，改为用Iterator的remove即可。

public static void doRemoveStr2(ArrayList<String> list) {
       Iterator<String> it = list.iterator();
       while (it.hasNext()) {
           String s = it.next();
           if (s.equals("str2")) {
               it.remove();
           }
       }
   }

One more thing

如果把之前的list元素改为如下：

public static void main(String[] args) {
    List<String> list = new ArrayList<String>();
    list.add("str1");
    list.add("str2");
    list.add("str3");
    for (String s : list) {
        if ("str2".equals(s)) {
            list.remove(s);
        }
    }
    System.out.println(list);
}

各位一定会觉得此时还会抛著名的ConcurrentModificationException吧？可实际的结果是，正确的输出了[str1,str3]。

这就还需要看一下AbstractList内部类Itr中的hasNext

public boolean hasNext() {
       return cursor != size();
}

当元素”str2”被删除后，cursor的值正好与数组的size()相等，所以Itr的遍历任务已经结束，不再会去获取下一个元素，所以也就没有抛异常了。当然这个情况只有在删除数组中的倒数第二个元素时才会出现，只是一个巧合现象，在开发中，我们还是绝对禁止在遍历list的时候直接使用list.remove()方法来删除元素的。

赏

感谢支持

支付宝

微信