ArrayList与LinkedList的遍历删除元素方法

简介: ArrayList与LinkedList的遍历删除元素方法

List的遍历删除元素方法

示例ArrayList

首先使用ArrayList的构造方法生成一个List实例list

List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C", "D", "E", "F", "G", "H", "I"

for loop(从后往前)

在使用for loop删除ArrayList的元素时,只能采用从后往前遍历的方法:

for (int i = list.size() - 1; i >= 0; i--) {
    if ("C".equals(list.get(i)) || "D".equals(list.get(i))) {
        list.remove(i);
    }
}
System.out.println(list);


这时打印list可以看到如下结果:

[A, B, E, F, G, H, I, J, K]

删除是成功的;

如果使用for loop从前往后遍历去删除元素,

for (int i = 0; i < list.size(); i++) {
    System.out.println(i + ":" + list.get(i));
    if ("C".equals(list.get(i)) || "D".equals(list.get(i))) {
        list.remove(i);
    }
}
System.out.println(list);


则运行结果:

0:A
1:B
2:C
3:E
4:F
5:G
6:H
7:I
8:J
9:K
[A, B, D, E, F, G, H, I, J, K]

可以看到,删除一个元素后,相邻的下一个元素是被遗漏了的,没有被遍历到,造成D没能被删除;

Iterator

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String s = iterator.next();
    if ("C".equals(s) || "D".equals(s)) {
        iterator.remove();
    }
}
System.out.println(list);

运行结果如下:

[A, B, E, F, G, H, I, J, K]

可以看到删除是成功的;

for each(不可使用)(fail-fast 机制)

for (String s : list) {
    if ("C".equals(s)) {
        list.remove(s);
    }
}
System.out.println(list);


会报错:

Exception in thread "main" java.util.ConcurrentModificationException
  at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:911)
  at java.util.ArrayList$Itr.next(ArrayList.java:861)


为什么会报这个错误呢?来看下对应的字节码:

Iterator var2 = list.iterator();
while(var2.hasNext()) {
    String s = (String)var2.next();
    if ("C".equals(s)) {
        list.remove(s);
    }
}

其实forEach在遍历的时候也是转换成Iterator的,但是删除时采用的是ArrayListremove()方法。

再来看下报错的源码:

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;
  ......
    @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();
    }
}


可以发现在执行next()函数时,发生报错,报错原因是modCount != expectedModCount;

modCount是AbstractList抽象类的一个变量,而expectedModCount是Itr类的一个变量;expectedModCount一开始被初始化为modCount,那么肯定是由于modCount或expectedModCount的值发生了变化导致两者不一致,从而触发了checkForComodification()中的ConcurrentModificationException()。


经过检查发现,ArrayList中的remove()方法会使modCount增加1

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 void fastRemove(int index) {
    modCount++;
    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
}


其实这是Java中的fail-fast机制,用来防止多线程并发修改同一集合的内容。


事实上,ArrayList的add()方法、remove()方法、addAll()方法(实际上是遍历使用add()方法),都会造成modCount的增加,从而导致modCount != expectedModCount,引发ConcurrentModificationException()。


特殊情况:

当使用Iterator来遍历但使用ArrayList的remove()方法来删除倒数第二个元素时,可以不报错且删除成功。

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String s = iterator.next();
    if (s.equals("J")) {
        list.remove(s);
    }
}
System.out.println(list);


运行结果:

[A, B, C, D, E, F, G, H, I, K]


这是为什么呢?

因为J刚好是倒数第二个元素,删除该元素之前cursor值为9size值为11,删除该元素之后,再次进入hasNext()方法,cursor值为10size值为10,不再进入next()方法,从而不会报错,但实质上,最后一个元素K并未进入循环。


我们来验证一下,用这种方法删除最后两个元素,看看运行结果怎样;

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String s = iterator.next();
    if (s.equals("J") || s.equals("K")) {
        list.remove(s);
    }
}
System.out.println(list);


运行结果依然是:

[A, B, C, D, E, F, G, H, I, K]

所以最后一个元素K没能进入循环。

removeIf

list.removeIf(s -> "C".equals(s) || "D".equals(s));
System.out.println(list);

运行结果如下:

[A, B, E, F, G, H, I, J, K]

看一下removeIf()方法的源码:

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;
}


其实removeIf()方法在底层是使用Iterator去进行了一个遍历,移除所有符合filter条件的元素;

stream().filter():

list.stream().filter(e -> !("C".equals(e) || "D".equals(e))).collect(Collectors.toList());
System.out.println(list);


运行结果如下:

[A, B, C, D, E, F, G, H, I, J, K]

可以看到未能成功删除CD,这是为什么呢?

其实filter并未在ArrayList本身做修改,而是返回了一个新的ArrayList,所以输出原来的list并不能得到删除后的结果;

用一个ArrayList去接收filter返回的数据并显示即可;

List<String> newList = list.stream().filter(e -> !("C".equals(e) || "D".equals(e))).collect(Collectors.toList());
System.out.println(newList);


输出结果:

[A, B, E, F, G, H, I, J, K]


删除成功。

LinkedList的遍历删除元素方法与ArrayList的区别

  1. 使用for loop时,由于LinkedListget(index)方法需要从首部或尾部元素进行遍历查找,因此效率较低;
目录
相关文章
|
6月前
|
存储 安全 Java
32.C#:ArrayList集合
32.C#:ArrayList集合
40 1
|
安全
ArrayList 和 LinkedList 的区别【重要】
ArrayList 和 LinkedList 的区别【重要】
65 0
|
6月前
|
存储 安全
ArrayList 和 LinkedList 的区别
ArrayList 和 LinkedList 的区别
|
存储 算法
遍历 ArrayList和遍历 Map的几种方式
遍历 ArrayList和遍历 Map的几种方式
66 0
|
Java
ArrayList与LinkedList遍历方式对比及List遍历技巧
ArrayList与LinkedList遍历方式对比及List遍历技巧
85 0
|
自然语言处理 Java
遍历list时删除元素发生了什么?
遍历list时删除元素发生了什么?
114 0
|
存储 程序员 索引
List集合和其子类ArrayList、LinkedList
List集合和其子类ArrayList、LinkedList
133 1
|
缓存 安全 算法
ArrayList 可以完全替代数组吗?
在前面的文章里],我们学习了很多数据结构与算法思想。在实际的业务开发中,往往不需要我们手写数据结构,而是直接使用标准库的数据结构 / 容器类。 在后续的文章里,我们将以 Java 语言为例,分析从 ArrayList 到 LinkedHashMap 等一系列标准库容器类,最后再有一篇总结回顾,请关注。
133 0
|
安全 Java 容器
如何在遍历的同时删除ArrayList 中的元素
如何在遍历的同时删除ArrayList 中的元素
408 0