列表在Java中使用for循环迭代时从ArrayList或LinkedList中删除元素？若然，原因为何？

Question

我向某人展示我的代码，他们说这会导致未定义的行为。作为一名Java程序员，我对这一点不是很了解。在下面的代码块中，我将遍历scenes，这是一个ArrayList，并从中删除元素

for(int i = 0; i < scenes.size() - 1; i++)
    {
        if(!(Double.valueOf(scenes.get(i + 1)) - Double.valueOf(scenes.get(i)) > 10))
        {
            scenes.remove(i + 1);
            i--;
        }
    }

这会编译，并且在运行时不会抛出异常，但我仍然不确定这是否是编程问题，为什么是编程问题，以及正确的方法是什么。我听说过使用Iterator.remove()和创建一个全新的List

Answer 1

在ArrayList中，从列表中间删除一个元素需要将索引较高的所有元素下移一。如果你只做一次（或几次）就可以了，但如果你重复做的话效率会很低

你也不想用Iterator来解决这个问题，因为Iterator.remove()也有同样的问题

更好的方法是浏览列表，将想要保留的元素移动到新位置；然后去掉列表末尾的部分：

int dst = 0;
for (int src = 0; src < scenes.size(); ++dst) {
  // You want to keep this element.
  scenes.set(dst, scenes.get(src++));

  // Now walk along the list until you find the element you want to keep.
  while (src < scenes.size()
         && Double.parseDouble(scenes.get(src)) - Double.parseDouble(scenes.get(dst)) <= 10) {
    // Increment the src pointer, so you won't keep the element.
    ++src;
  }
}

// Remove the tail of the list in one go.
scenes.subList(dst, scenes.size()).clear();

（这种“移位并清除”的方法是ArrayList.removeIf所使用的方法；这里不能直接使用这种方法，因为不能检查列表中的相邻元素，只能访问当前元素）

---

您可以采用类似的方法，该方法也可以有效地处理非随机访问列表，例如LinkedList。您需要避免重复调用get和set，因为在LinkedList的情况下，它们是O(size)

在这种情况下，可以使用ListIterator而不是普通索引：

ListIterator<String> dst = scenes.listIterator();
for (ListIterator<String> src = scenes.listIterator(); src.hasNext();) {
  dst.next();
  String curr = src.next();
  dst.set(curr);

  while (src.hasNext()
         && Double.parseDouble(src.next()) - Double.parseDouble(curr) <= 10) {}
}
scenes.subList(dst.nextIndex(), scenes.size()).clear();

或者类似的。我还没有测试过它，而且ListIterator使用起来总是很混乱

Answer 2

这很简单，适用于ArrayList或LinkedList：

        Iterator<String> iterator = list.iterator();
        double current = 0;
        double next;
        boolean firstTime = true;
        while (iterator.hasNext()) {
            if (firstTime) {
                current = Double.parseDouble(iterator.next());
                firstTime = false;
            } else {
                next = Double.parseDouble(iterator.next());
                if (next - current > 10) {
                    current = next;
                } else {
                    iterator.remove();
                }
            }
        }