for-each vs for vs while

Question

I wonder what is the best way to implement a "for-each" loop over an ArrayList or every kind of List.

Which of the followings implementations is the best and why? Or is there a best way?

Thank you for your help.

List values = new ArrayList();

values.add("one");
values.add("two");
values.add("three");
...

//#0

for(String value : values) {
    ...
}

//#1

for(int i = 0; i < values.size(); i++) {
    String value = values.get(i);
    ...
}

//#2

for(Iterator it = values.iterator(); it.hasNext(); ) {
    String value = it.next();
    ...
}

//#3

Iterator it = values.iterator();
while (it.hasNext()) {
    String value = (String) it.next();
    ...
}

Answer 1

#3 has a disadvantage because the scope of the iterator it extends beyond the end of the loop. The other solutions don't have this problem.

#2 is exactly the same as #0, except #0 is more readable and less prone to error.

#1 is (probably) less efficient because it calls .size() every time through the loop.

#0 is usually best because:

• it is the shortest
• it is least prone to error
• it is idiomatic and easy for other people to read at a glance
• it is efficiently implemented by the compiler
• it does not pollute your method scope (outside the loop) with unnecessary names

Answer 2

The short answer is to use version 0. Take a peek at the section title Use Enhanced For Loop Syntax at Android's documentation for Designing for Performance. That page has a bunch of goodies and is very clear and concise.

Answer 3

#0 is the easiest to read, in my opinion, but #2 and #3 will work just as well. There should be no performance difference between those three.

In almost no circumstances should you use #1. You state in your question that you might want to iterate over "every kind of List". If you happen to be iterating over a LinkedList then #1 will be n^2 complexity: not good. Even if you are absolutely sure that you are using a list that supports efficient random access (e.g. ArrayList) there's usually no reason to use #1 over any of the others.

Answer 4

In response to this comment from the OP.

However, #1 is required when updating (if not just mutating the current item or building the results as a new list) and comes with the index. Since the List<> is an ArrayList<> in this case, the get() (and size()) is O(1), but that isn't the same for all List-contract types.

Lets look at these issues:

It is certainly true that get(int) is not O(1) for all implementations of the List contract. However, AFAIK, size() is O(1) for all List implementations in java.util. But you are correct that #1 is suboptimal for many List implementations. Indeed, for lists like LinkedList where get(int) is O(N), the #1 approach results in a O(N^2) list iteration.

In the ArrayList case, it is a simple matter to manually hoist the call to size(), assigning it to a (final) local variable. With this optimization, the #1 code is significantly faster than the other cases ... for ArrayLists.

Your point about changing the list while iterating the elements raises a number of issues:

• If you do this with a solution that explicitly or implicitly uses iterators, then depending on the list class you may get ConcurrentModificationExceptions. If you use one of the concurrent collection classes, you won't get the exception, but the javadocs state that the iterator won't necessarily return all of the list elements.

• If you do this using the #1 code (as is) then, you have a problem. If the modification is performed by the same thread, you need to adjust the index variable to avoid missing entries, or returning them twice. Even if you get everything right, a list entry concurrently inserted before the current position won't show up.

• If the modification in the #1 case is performed by a different thread, it hard to synchronize properly. The core problem is that get(int) and size() are separate operations. Even if they are individually synchronized, there is nothing to stop the other thread from modifying the list between a size and get call.

In short, iterating a list that is being concurrently modified is tricky, and should be avoided ... unless you really know what you are doing.