List遍历remove的那些事

在工作中经常写代码时会遇到遍历list并且过滤的一些逻辑，现在来看一下不同的遍历的优劣：

case在50000的范围内过滤3和7的倍数

先看一个案例

 

这个是以7为倍数，看结果大家可能以为过滤没问题,大家其实别被表象误导，其实遍历到49的时候就会出现错误(7*7=49)，只是此时可能没看出来，来一个比较明显的：加一个条件再过滤3的呢。

可以看到7为倍数的数字没被过滤，而这个就是直接循环使用remove容易出现的bug，真正原因看下内部的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;
    }

    /*
     * Private remove method that skips bounds checking and does not
     * return the value removed.
     */
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            //remove会导致之后的元素往前移动，而下标不改变时就会出现bug
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }

1.正确的做法应该是这样:

耗时：200ms左右

2.再看一下foreach遍历的：

报了一个错误异常，而想了解其中真正的原因需要知道foreach的内部实现，foreach其实是用迭代器来进行遍历的，而在遍历时直接使用arraylist的remove方法会导致什么问题呢？

可以再看一下fastremove和迭代器遍历的内部代码:

最后导致抛出上面异常的其实就是这个

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
        //调用next时会调用checkForComodification方法检查 这两个字段
        //而fastRemove里面只对modCount 进行了改变 导致抛出异常
        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];
        }

所以遍历时remove并不适用于foreach，接下来再看一下迭代器的效果

3.

耗时:150ms左右

使用迭代器的好处呢就是不用关注下标的变化和内部的实现，本来这也就是责任链设计模式想达到的效果，并且可以看到效果也比普通遍历要稍好一点,当然目前的list的遍历可不止这些，继续往下探索:

4.使用复制list

耗时：60ms左右

可以看到这次的效率就比较突出了，而只要的原因呢？

其实是因为以ArrayList为例的内部remove方法（前面有fastRemove代码就不贴了）也肯定是会比较消耗系统资源的，而直接将符合条件的元素add到其他的list中肯定效率是会更加高效的

 

接下来进入JDK8的时代，其中遍历list的花样也就增加了

5.java8的新方法removeIf()

耗时：150ms左右

和迭代器的效率差不多，看下内部实现其实就知道了：

    //内部其实就是迭代器遍历
    default boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        boolean removed = false;
        final Iterator<E> each = iterator();
        while (each.hasNext()) {
            if (filter.test(each.next())) {
                each.remove();
                removed = true;
            }
        }
        return removed;
    }

6.Stream:

使用java8中的stream来进行list过滤：

耗时：150ms左右

以上都是以ArrayList为例，现在来看一下LinkList的不同效果呢：

7.LinkList的复制

耗时：150ms左右    

8. LinkList的迭代器:

耗时：150ms左右

之前效果突出的复制list的做法在LinkList上却感觉没什么效果了？  知道LinkList的原理想清楚也就不难了，LinkList内部是一个链表，而链表中的添加和删除节点都是O(1)的复杂度，但是缺点是遍历查找某一个元素的时间复杂度为O(n)就比较高了

 

从以上初步测试中可以得到以下几个结论：

1----在不考虑内存大小会不会出现OOM的时候，采取复制一个满足条件的新list速度更快，适用于集合中的对象不算多时，毕竟只需要add操作,并且ArrayList的速度大于Linklist，因为链表在循环遍历时是很慢的

.

2----当集合中的元素过多过大时，第一种方案就不行，但是现实场景中比较少见，采用迭代器的方式进行遍历是较快的，并且也不用专注下标的变化，ArrayList和LinkList的速度也差不多

 

3----不考虑性能使用removeIf方法代码更加简洁明了

 

3----在forEach遍历时不能使用list.remove()方法，否则会抛ConcurrentModificationException异常

 

4----链表无论是使用复制还是迭代器进行删除元素速度都差不多

 

因此究竟在采用那种list集合或者方式进行元素遍历时的删除时，都需要根据不同的场景来定