遍历列表时删除列表上的元素

我需要一种在迭代过程中删除List上的元素的方法。

应该是这样的（非法代码）：

br />
但是我们都知道上面的代码是不允许的。

所以我现在正在做的是创建另一个List，在其中放置每个满足给定条件，然后遍历该List以获取需要在第一个List上删除的元素。

List<Integer> nums = new ArrayList();
nums.add(1);
nums.add(2);
nums.add(3);
...
nums.add(10);

System.out.println("BEFORE REMOVE: " + nums);

for (Integer integer : nums) {
    if (integer < 3) {
        //not allowed
        nums.remove(integer);
    }
}

我知道还不长，但是有更好的方法吗？

是否有一些我可以使用的API ？

我认为您可以使用nums.removeAll（toRemove）

#1 楼

有几种方法可以做到这一点。让我们看一下替代方法：在副本上迭代，从原始副本中删除

这是解决第一个代码的基本问题的简单解决方案：抛出ConcurrentModificationException是因为您遍历列表并同时从列表中删除。

简单的解决方案是创建列表的副本并遍历列表。

for (Integer integer : new ArrayList<>(nums)) {
    if (integer < 3) {
        nums.remove(integer);
    }
}

这种方法的缺点：

创建原始列表的副本，该副本需要内存，并且操作的性能取决于列表的类型（ArrayList，LinkedList，等。）
另外，nums.remove(value)是\ $ O（n）\ $运算。使此循环整体为\ $ O（n ^ 2）\ $

Java 8流

List<Integer> filteredList = nums.stream().filter(i -> i >= 3).collect(Collectors.toList());

缺点：

实际上并没有修改现有列表，因此，如果对该列表的引用分散在各个变量中，那么您仍然会有一些旧元素，这些元素不应该包含在该列表中。 />创建各种与流相关的对象，这些对象可能不是最有效的选择。

从正面看，这是大型列表中最快的对象。

如果不使用Java 8：

List<Object> originalList;
List<Object> newList = new YourFavoriteListType<>();
for (Object obj : originalList) {
    if (shouldKeep(obj)) {
        newList.add(obj);
    }
}

Java 8方法

nums.removeIf(i -> i < 3);

Java 8引入了默认方法removeIf接口上的Collection。这允许不同的实现对该方法具有特定于实现的性能进行优化的实现。

Iterator.remove（）

Iterator<Integer> it = nums.iterator();
while (it.hasNext()) {
    Integer integer = it.next();
    if (integer < 3) {
        it.remove();
    }
}

唯一的缺点这种方法的另一面是您需要将for-for切换为while。但是，这种方法是最有效的方法，尤其是对于LinkedList，它是\ $ O（n）\ $（对于ArrayList是\ $ O（n ^ 2）\ $，因为它必须在每个remove(index)调用中复制数组数据）。这是我在大多数情况下建议使用的方法。 />结论

如果您想对现有列表进行变异，removeIf是我可以使用的解决方案。如果您喜欢函数式编程，并且希望使用新列表而不是对现有列表进行变异，那么请使用list.stream().filter(...).collect(Collectors.toList())方法。 ”堆栈溢出

\ $ \ begingroup \ $
LinkedList为O（n），而ArrayList为O（n ** 2）。迭代器无法做任何避免数据移动的事情。
\ $ \ endgroup \ $
– maaartinus
2014-09-27 15:45

\ $ \ begingroup \ $
@maaartinus是的，但这确实取决于System.arraycopy的实现方式，因为它是本机调用。我倾向于将其视为纯内存复制调用，我更认为它是O（1）而不是O（n），但是从SO答案来看，它似乎很可能是O（n）。
\ $ \ endgroup \ $
–西蒙·福斯伯格
2014-09-27 15:52

\ $ \ begingroup \ $
当Java非常慢时，它曾经是本地调用。不再是魔术子弹了。现在，它是JVM固有的，这意味着JITc可以用智能，快速的方式（使用XMM寄存器）替换代码。但是它仍然是O（n）。我可以想象虚拟内存映射会鬼混，这会更快，但仍然是O（n）。无论如何，它将适用于偏移量是页面大小的倍数的情况，所以让我们忘记它。
\ $ \ endgroup \ $
– maaartinus
2014-09-27 15:59

\ $ \ begingroup \ $
@maaartinus要为ArrayList保留O（n），只需循环并在单独的集合中收集要删除的所有元素，然后在ArrayList上调用removeAll（）。
\ $ \ endgroup \ $
– Bowmore
2014-09-28 8:16

\ $ \ begingroup \ $
@bowmore是的，但是单独的必须具有O（1）访问权限。因此，您需要像HashMap这样的东西，它又具有相当高的开销（不是很高，但与列表相比却很高）。我敢打赌，收集第二个列表中的所需元素至少要快3倍。
\ $ \ endgroup \ $
– maaartinus
2014年9月29日在18:26

#2 楼

只是不得不做一些非常相似的事情（因此我为什么要在这里），最终使用了Java8的Collection.removeIf(Predicate<? super E> filter)

与您的代码类似：
如果您想收集移除物品：

nums.removeIf((Integer i)->{return i<3;});

\ $ \ begingroup \ $
我喜欢Java 8的这种方式，因为它更加简洁，同时仍然足够清晰。但是，在内部（查看JDK代码），它似乎仍使用迭代器并调用iterator.remove（）。因此，其他职位中列出的性能注意事项仍然有效。
\ $ \ endgroup \ $
– kg_sYy
2015年10月24日在14:17

#3 楼

在其他提出的解决方案中，除使用Java 8的解决方案外，其他解决方案似乎都是O(n**2)，即，当list（*）变得更大时，它太慢了。

最简单的快速解决方案是创建一个空列表，并添加不少于三个元素。

如果需要修改原始列表，请随后清理并添加辅助列表中的所有元素。 br />（*）除非它是LinkedList，否则在这里很出色。但是它在所有其他情况下的性能都非常糟糕，几乎不应该使用。

#4 楼

除了@Simon的答案外，您还可以使用反向的for循环遍历数组以删除不需要的项。由于remove方法，它仍然是O（n ^ 2）运算。因此，这种方法并没有更好，但它是另一种实现方法。

for(int index = array.size() - 1; index >= 0; index--) {
    if(array.get(index) < 3){
        array.remove(index);
    }
}

\ $ \ begingroup \ $
它有点快，因为它不移动任何元素以备以后删除。但同意，它仍然是O（n ** 2）。
\ $ \ endgroup \ $
– maaartinus
2014年9月27日下午16:34

\ $ \ begingroup \ $
array.get是对LinkedList的缓慢操作，最好使用能够向后移动的array.listIterator（）。
\ $ \ endgroup \ $
–西蒙·福斯伯格
2014-09-27 17:33

\ $ \ begingroup \ $
但是，使用老式的for循环进行迭代确实可以解决ConcurrentModificationException。（即使它是前向的，您也可以在每次删除项目时降低索引）
\ $ \ endgroup \ $
–西蒙·福斯伯格
2014-09-27 17:34

\ $ \ begingroup \ $
好吧，OP有一个Arraylist <>，所以我选择了ArrayList！而且我发现使用反向循环而不是弄乱循环内的索引更加清楚
\ $ \ endgroup \ $
–IEatBagels
2014-09-27 18:56

\ $ \ begingroup \ $
因为ArrayList.get是O（1）操作
\ $ \ endgroup \ $
–IEatBagels
2014-09-27 18:57

#5 楼

另一个可能有趣的选择是使用CopyOnWriteArrayList：从类名来看，缺点很明显：在每次写操作之前，它都会复制基础列表。此类用于观察员列表，该列表很少被修改且经常被遍历。我不确定这是否适用于您的情况（如果从列表中删除是否频繁），但我想我只是为了以防万一。

编程黑洞网