在浏览列表时删除列表的随机元素

Question

从我读到的内容来看，在迭代列表时删除元素是安全的。(而不是为每个循环使用简单(。

假设我有一个元素列表，我想访问所有元素，

但是当我访问每个元素时，我将访问它的邻居(请注意，我为每个元素绘制了一张地图，它将给我它的邻居(，因此我将必须从原始列表中删除其他元素。因此我不能使用iterator.remove((.

这样做的好方法是什么，也就是说，从我正在经历的列表中删除元素，而无需处于迭代器的位置？

我的

一个想法是，将我的元素放在地图中，其值为一个布尔值，(对于访问过为真，否则为假(。因此，我浏览了我的列表，对于我设置的每个元素，它都访问了 true，如果一个如果它的邻居我在访问该元素时也看到，我也会将它们设置为 true。

Answer 1

使用 for 循环而不是 foreach 来迭代项目。然后根据需要取下。 下面是从列表中删除偶数元素的示例

import java.util.List;
import java.util.ArrayList;
class Test {
    public static void main(String[] args){
            final List<Integer> ints = new ArrayList<Integer>();
            ints.add(100);
            ints.add(1);
            ints.add(15);
            ints.add(42);
            ints.add(187);
            System.out.println("Original List");
            for(Integer i: ints){
                    System.out.println(i);
            }
            /* Remove any even elements from the list */
            for(int i=0; i < ints.size(); i++){
                    if(ints.get(i) % 2 == 0){
                            ints.remove(i);
                    }
            }
            System.out.println("nModified List");
            for(Integer i: ints){
                    System.out.println(i);
            }
    }
}

Answer 2

假设您正在谈论一个ArrayList输入列表。

以下方法将为您提供O(N)行为(至少对于 OpenJDK Java 6 到 Java 8(：

1. 创建哈希集。

2. 遍历输入列表的元素：

   1. 访问该元素并将其添加到集合中(如果应将其删除(
   2. 访问元素的邻居，并将任何应删除的元素添加到集合中。

3. 呼叫list.removeAll(set) 。

ArrayList的removeAll方法调用内部batchRemove方法(请参阅此处(。 这种方法对ArrayList的后备阵列执行单次传递，删除元素并填充孔。 它测试每个元素以查看是否应通过调用 set.contains(elem) 将其删除。 对于一个HashSet，该测试是O(1)的，因此removeAll(set)调用是O(N)其中N是列表大小。

---

有趣的是，arrayList.removeAll(hashSet) 将O(N)其中N是列表长度，但删除相同的元素，如下所示：

for (Iterator it = arrayList.iterator; it.hasNext(); ) {
      if (hashSet.contains(it.next())) {
             it.remove();
      }
}

将O(NM)其中N是列表长度，M是设置大小。