5

我有以下声明：

ArrayList<String> list = new ArrayList<String>();
list.add("1");
list.add("2");
list.add("2");
list.add("3");
list.add("4");

现在我的问题是：如果我想从列表中删除“2”，哪种方式更好？

第一种方式：

for(int i = 0; i < list.size(); i++) {
    if(list.get(i).equals("2")) {
        list.remove(i);
        i--;
    }
}

第二种方式：

Iterator<String> iterator = list.iterator();
    while(iterator.hasNext())
        if(iterator.next().equals("2"))
            iterator.remove();

两者都得到妥善保护，哪个更有效？

有没有其他方法可以从 ArrayList 中删除元素而不会IndexOutOfBounds出错？

4

4 回答 4

5

实际上，可能更快的是

list.removeAll(Collections.singleton("2"));

在幕后，对于 a ArrayList，它基本上确实像@Edmund 建议的那样创建了数组的新副本，但是在较低级别上，这可能会带来更高的性能。

尽管如此，正如其他人所提到的，LinkedList从大列表中删除多个元素通常具有更好的性能。

（即使您决定切换到 aLinkedList您仍然可以使用上面的代码，这将等同于使用迭代器方法，但会为创建的单例集合和发生的一些额外方法调用带来一点开销。）

于 2012-04-16T01:44:30.960 回答
2

无论哪种方式都需要为每个删除的元素向下移动元素。如果您的列表真的很大，那么创建一个新列表可能会更快：

ArrayList<String> newList = new ArrayList<String>();
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String val = iterator.next();
    if(!val.equals("2"))
        newList.add(val);
}

/* Or just return newList, depending on how list is used in subsequent code. */
list.clear();
list.addAll(newList);

您可以考虑使用LinkedList而不是ArrayList. 但是基准测试（使用实际用例）是找出最有效的最佳方法。

于 2012-04-16T01:25:52.273 回答
0

对于单个元素，您的 for 循环可以正常工作（好吧，当您删除时它会i---remove()自动将元素移到左侧）（真的，它会正常工作）。你的迭代方法也是如此。

你只是迭代到 的末尾ArrayList，你不会离开它。就效率而言，这是一种洗礼——我建议您对大小为 100,000 的运行时进行采样，看看效果如何。（无论列表有多大，它仍然是 O(N) 操作的顺序。）

于 2012-04-16T01:24:13.173 回答
-1

我在一些数据结构书籍中读过，迭代器方法更好，

如果在循环下调用list.remove，evety时间将从0索引开始到索引ot项删除，然后删除元素并移动受影响的元素，这将是o（n2）过程。

但是在 iterator.remove 的情况下，元素在被迭代器访问时被删除，而不必在列表的开头返回，因此是 o(n) 过程。

于 2012-04-16T01:41:02.013 回答