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
的,但是删除时采用的是ArrayList
的remove()
方法。
再来看下报错的源码:
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
值为9
,size
值为11
,删除该元素之后,再次进入hasNext()
方法,cursor
值为10
,size
值为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]
可以看到未能成功删除C
和D
,这是为什么呢?
其实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的区别
- 使用
for loop
时,由于LinkedList
的get(index)
方法需要从首部或尾部元素进行遍历查找,因此效率较低;