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

这是编译的，在运行时不会抛出异常，但我仍然不确定这是否是一个编程no，为什么是编程no，以及正确的方法是什么。我听说过使用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();
}
}
}