什么是遍历列表的最佳方式？

Question

我在集合方面工作了很多，但还有一些疑问。

我知道我们可以使用迭代器来遍历列表。

另一种方法是按以下方式进行：

for(int i=0; i<list.size(); i++){
   list.get(i);
}

我认为这里存在一个问题，每次调用list.size()都会构建整个树，影响性能。

我也考虑了其他解决方案，例如：

int s = list.size();
for(int i=0; i<s; i++){
  list.get(i);
}

我认为这可以解决问题。我对线程不是很熟悉，但我在考虑这种方法是否正确。

另一种我想到的方法是：

for (Object obj; list){

}

通过这个新的循环，我认为编译器会再次检查列表的大小。

请从中选择最佳解决方案或替代性能效率方法。感谢您的帮助。

- Nimesh

---

为什么list.size()会构建整个树结构？ - ChiefTwoPencils

JVM 应该能够缓存 list.size() 的值，以便不必每次都调用该函数。 - lschuetze

Answer 1

在每次迭代中调用size()并不是真正的问题。对于我所知道的所有集合，此操作的时间复杂度均为O(1)： size()只返回列表的一个字段的值，该字段保存其大小。

第一种方法的主要问题是重复调用get(i)。对于ArrayList，此操作的时间复杂度为O(1)，但对于LinkedList，它的时间复杂度为O(n)，使整个迭代的时间复杂度从O(n)变为O(n²)： get(i)强制列表从第一个元素（或最后一个元素）开始，并到下一个节点，直到第i个元素。

使用迭代器或使用foreach循环（内部使用迭代器）可以保证使用最适当的迭代方式，因为迭代器了解列表的实现方式以及如何最好地从一个元素移到下一个元素。

顺便说一句，这也是遍历非索引集合（如Set）的唯一方法。所以最好习惯使用这种类型的循环。

- JB Nizet

---

那么新的for循环呢？ - Nimesh

这就是我所说的“foreach循环”。它在内部使用迭代器。我倾向于避免称其为“新for循环”，因为它根本不是新的，已经有10年历史了。 - JB Nizet

是的，但从身份的角度来看，我们称其为新的for循环。 - Nimesh

正确的术语，由Java语言规范使用，是"增强型for语句"。但不管信不信，它通常被称为foreach循环。例如请参考：https://docs.oracle.com/javase/1.5.0/docs/guide/language/foreach.html - JB Nizet

是的，但作者无法正确地进行基准测试。那很难，他的基准测试完全有缺陷。 - JB Nizet

Answer 2

对于您的例子，这是最佳方式：

for (Object obj: list){

}

这与Java版本<1.5相同：

for (Iterator it = hs.iterator() ; it.hasNext() ; ){}

它使用集合的迭代器。实际上您不需要知道集合的大小。.size() 方法应该不会构建树，而 .get() 可以循环到给定的元素。.get() 和 .size() 方法取决于 List 的实现。在 ArrayList 中，.get() 应该是 O(1) 复杂度而不是 O(n)。

更新

在 Java 8 中，您可以使用：

myList.forEach{ Object elem -> 
 //do something
}

- CyberAleks

Answer 3

for (Object obj: list){

}

对我来说，上面的代码是最好的方式，它很简洁，易于阅读。

Java 8中的forEach也很不错。

- shepard23

Answer 4

在性能方面，迭代列表的最佳方法是使用迭代器（第二种方法使用foreach）。如果您使用list.get（i），则其性能将取决于列表的实现。对于ArrayList，list.get（i）是O（1），而对于LinkedList，则为O（n）。

此外，list.size（）是O（1），不应对性能产生任何影响。

- Mohit Gupta

---

forEach的时间复杂度是多少？如果它是O(n)，为什么设计师不选择O(log n)呢？ - balboa_21