遍历数据时arraylist效率高于linkedlist_遍历问题种类

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

概述

一个 java 程序猿比较广为人知的小知识 ，是 ArrayList 和 LinkedList 最好使用迭代器删除，而不是遍历删除。

当我们尝试使用 for 循环或者 forEach 进行删除的时候，往往会出现一些意外的情况，导致集合全部删除失败。关于这点，我一直保持知其然不知其所以然的状态，刚好最近刚看完 ArrayList 和 LinkedList 的源码，今天这篇文章，就结合源码，总结一下 ArrayList 和 LinkedList 的几种错误删除。

一、List 集合的 fast-fail 机制

在开始前，我们需要了解一下集合的 fast-fail 机制。

List 接口有一个 AbstractList 抽象类，List 下的所有实现类都直接或间接的继承了它。

在它的成员变量中，有一个变量叫 modCount，当实现类进行结构性操作的时候——一般指会影响底层数据结构的操作，比如删除——就会+1。

在每一个迭代器创建的时候，会从外部获取当前的 modCount赋给迭代器的成员变量 expectedModCount，然后每次调用迭代器的 next()方法，或者其他增删方法都会比较modCount和expectedModCount是否相等，否则就会抛出 ConcurrentModificationException 异常。

这个并发修改检查可以在出现问题是时候快速抛出异常，避免可能错误的数据进入后续的操作。这也是集合操作中大部分 ConcurrentModificationException 异常的来源。

二、ArrayList 的 for 循环删除

ArrayList 的 remove()有根据下标删除与根据元素删除两种，后者每次删除必然需要先遍历集合，效率非常低，所以这里只讨论前者，也就是根据下标删除的方法。

1.实例

我们知道， ArrayList 底层实现是数组，他又实现了 RandomAccess 的接口，因此官方是推荐使用 for 循环去操作遍历集合的。但是当我们使用 for + 下标删除 ArrayList 中的元素时，会发生“漏删”的问题。

我们来模拟一下：

ArrayList<String> list = new ArrayList<>(Arrays.asList("a","b","c","d"));
for (int i = 0; i < list.size(); i++) {
    list.remove(i);
}
System.out.println(list); // [b, d]

可见，b 和 d 被跳过了。

2.原因

我们可以看看 ArrayList 中 remove()方法的源码:

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++
    modCount++;
    int numMoved = size - index - 1;
    // 是否需要移动数组
    if (numMoved > 0)
        // 拷贝并且移动数组
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null;
}

在fastRemove()方法里，调用了数组拷贝的方法 System.arraycopy()，他将删除位置后的数组整体前移一位。

我们来复原一下这个删除的流程：

简单的来说，我把 index = a 的元素删掉了，那么原本 index = a + 1 的元素就会跑到 index = a 的位置，当开始下一次循环的时候，我们以为删的是 indedx = a + 1 的元素，其实是 index = a + 2 的元素，索引发生了“偏移”，这就是“漏删”的原因。

3.解决办法

要避免这种情况，有两种办法：

• 每次索引偏移以后都手动把 index–；
• 想办法不让索引“偏移”，也就是不调用 arraycopy()方法。

第一种办法是在偶次操作前让 index–

int size = list.size();
for (int i = 0, j = 0; i < size; i++, j++) {
    list.remove(j);
    if (j % 2 == 0) {
        j--;
    }
}
System.out.println(list); // []

实际上，这个思路也是 ArrayList 中迭代器的 remove() 思路，但是用 for 循环写出来的代码非常繁琐，而且不便于理解。

第二种办法是倒序删除

我们回去看看 fastRemove()，会看到这样一段代码：

int numMoved = size - index - 1;
// 是否需要移动数组
if (numMoved > 0) {
    ... ...
}

实际上，numMoved = szie - 1 - index决定了是否需要移动数组，也就是说，我们传入的 index 只要大于等于 size，就不会引起下标，那样我们可以倒序删除：

for (int i = list.size() - 1; i >= 0; i--) {
    list.remove(i);
}
System.out.println(list); // []

三、ArrayList 的 forEach 删除

1.实例

先说问题，ArrayList 在使用 forEach()循环删除的时候会抛异常：

ArrayList<String> list = new ArrayList<>(Arrays.asList("a","b","c","d"));
try {
    list.forEach(list::remove);
} catch (ConcurrentModificationException e) {
    System.out.println(list); // [b, c, d]
    e.printStackTrace(); // ConcurrentModificationException
}

在删除第二个元素的时候，这段代码抛异常了。

2.原因

ArrayList 的 forEach 方法来自 Collection 的父接口 Iterable，Iterable 的默认显示方式是增强 for 循环，而 ArrayList 重写了这个方法：

public void forEach(Consumer<? super E> action) {
    Objects.requireNonNull(action);
    // 获取当前 modCount
    final int expectedModCount = modCount;
    @SuppressWarnings("unchecked")
    final E[] elementData = (E[]) this.elementData;
    final int size = this.size;
    // 每次循环开始前检查 modCount
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        action.accept(elementData[i]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

forEach()开始就使用 expectedModCount 记录了方法开始时的 modCount，然后每次循环的时候和循环结束的时候都会判断 modCount == expectedModCount， 我们回头看看 ArrayList 的 remove()方法，会看到在 fastRemove()中开始就让 modCount++了，因此我们不难推断出这整个流程：

• forEach()，方法调用，此时expectedModCount = modCount = 0；
• 进入 for 循环，判断 expectedModCount = modCount通过，进行第一次遍历
• action.accept()中我们使用 lambda 表达式传入了 remove()方法，此时删除了第一个元素，并且 modCount++。现在 modCount=1
• 判断expectedModCount = modCount不通过，跳出循环
• 判断 modCount != expectedModCount通过，抛出异常

也就说，不止是删除，所有会导致 modCount增加的方法，都不可以在 forEach()中使用。

我们可以使用 add()检验看看：

ArrayList<String> list = new ArrayList<>(Arrays.asList("a","b","c","d"));
try {
    list.forEach(list::add); // [a, b, c, d, a]
} catch (ConcurrentModificationException e) {
    System.out.println(list);
    e.printStackTrace(); // ConcurrentModificationException
}

四、ArrayList 的迭代器删除

使用迭代器的方法删除是没问题的，但是如果在迭代器迭代过程中，调用了非迭代器的方法，就会出问题：

ArrayList<String> list = new ArrayList<>(Arrays.asList("a","b","c","d"));
try {
    Iterator<String> iterator = list.iterator();
    while (iterator.hasNext()) {
        String s = (String) iterator.next();
        // 使用非iterator的方法删除
        list.remove(s);
    }
} catch (ConcurrentModificationException e) {
    System.out.println(list); // [b, c, d]
    e.printStackTrace(); // ConcurrentModificationException
}

可以看到抛异常了，但是把 list.remove()换成 iterator.remove()就没问题。

我们可以看看 iterator.remove()的源码：

public void remove() {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();

    try {
        // 调用外部的remove方法
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        // 获取最新的 modCount
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

明显的，相比直接调用外部 remove() ，迭代器内部的 remove()在调用外部的 remove()以后，又更新了 expectedModCount，这个 expectedModCount是个迭代器内部的成员变量，在构造方法执行的时候从外部获取 modCount并赋给他，每一次调用迭代器的 next()方法前都会比较 expectedModCount 和 modCount，如果不相等就会抛异常。

至此问题就明了了，当我们不使用迭代器内部的 remove()删除节点的时候，modCount更新了，但是expectedModCount，因而在迭代第二个元素的时候就会抛出 ConcurrentModificationException 异常。

换句话说，和 forEach()一样，并不是只有 remove()才会引起如此问题，在迭代器迭代过程中，调用任何外部会导致 modCount改变的方法都会使其抛异常。

五、LinkedList 的 for 循环删除

LinkedList 的 for 循环删除也会导致“漏删”

LinkedList<String> list = new LinkedList<>(Arrays.asList("a","b","c","d"));
for (int i = 0; i < list.size(); i++) {
    list.remove(i);
}
System.out.println(list); // [b, d]

和 ArrayList 的 for 循环删除出错的原因一样，也是因为索引发生了“偏移”。但是和 ArrayList 不一样的是，由于 LinkedList 底层实现是链表，所以他不是通过 arraycopy()方法，而是直接解除了前后节点的引用关系：

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

解决方法和 ArrayList 一样，只要避免循环中索引“偏移”即可，ArrayList 中手动 index– 和倒序删除两种办法对他同样适用。

六、LinkedList 的 forEach 删除

ArrayList 中的 forEach()是重写了 Iterable 接口的 forEach()方法，但是 LinkedList 中没有重写，所以 LinkedList 的 forEach() 使用的仍然还是 Iterable 接口中提供的实现：

default void forEach(Consumer<? super T> action) {
    Objects.requireNonNull(action);
    for (T t : this) {
        action.accept(t);
    }
}

当我们使用增强 for 循环遍历数组的时候，最终编译以后得到的是 for + 下标的普通 for 循环，而遍历集合则会编译为迭代器版的循环。因此：

// forEach
list.forEach(list::remove);

// 增强for
for (T t : list) {
    list.remove(t);
}

// 迭代器
Iterator<T> iterator = list.listIterator();
while (iterator.hasNext()) {
    list.remove(iterator.next());
}

上面三种写法是等价的。在 LinkedList 中， forEach 遍历和迭代器遍历是等价的，前者到最后还是用的迭代器。而实际上，当我们看到迭代器里面的 list.remove()就应该明白 LinkedList 的 forEach()为什么会抛异常了。

和 ArrayList 的迭代器删除一样，由于调用的是外部的 remove()导致modCount改变，而expectedModCount没有改变，因此在调用next()的时候会因为过不了 expectedModCount = modCount而抛出 ConcurrentModificationException 异常。

七、总结

为什么有时候会抛出 ConcurrentModificationException 异常？

List 集合中存在并发修改检查机制，AbstractList 提供 modCount字段，当使用 add()或者 remove()这样结构性操作的方法时，会让 modCount + 1。List 实现类的迭代器在创建的时候，都会使用成员变量 expectedModCount 记录当前的 modCount，每次调用 next()的时候都会检查最新的 modCount与 expectedModCount是否相等，否则就抛出 ConcurrentModificationException 异常。

因此，只有调用迭代器内部提供的方法，才会同步更新expectedModCount，否则只会更新modCount。所以 ArrayList 与 LinkedList 在迭代器迭代过程中增删会抛异常。

ArrayList 重写了 forEach()方法，从增强 for 改为了普通的 for 循环，但是在方法最开始也记录了modCount，每次循环都会对比，因此也会因为在循环中改变了 modCount而抛异常。

LinkedList 未重写 forEach()方法，底层仍然使用增强 for，编译后还是迭代器，因此抛异常的原因同迭代器中操作。

为什么普通 for 循环删除会“漏删”？

ArrayList 的删除底层是使用 arraycopy方法生成了一个新数组，新数组上被删除节点以后的全部元素都会前移一位，导致了索引的“偏移”，因此删除了 a，那 a+1 的元素就会调到 a 的位置，下一次删除 a + 1 实际上是删除 a + 2，因此 a + 1 就被跳过了。

LinkedList 是链表，但是删除一个节点也会导致后一个节点“补到”被删除节点的下标对应的位置，因此同样也会因为索引“偏移”而出现“漏删”的情况。

解决方法是有两种，一种是在删除元素以后让索引继续指向当前位置，另一种是倒序删除。

其实如果添加元素的话也会有问题，虽然能够添加成功，但是不会按照指定的顺序插入，这也是因为上面这个原因。