2014-04-20

For-each loop vs Iterator vs C-style for loop

In Java a for loop that uses an iterator
List<String> strings = new LinkedList<>(Arrays.asList("first", "second"));
for (Iterator iterator = strings.iterator(); iterator.hasNext();) {
    System.out.println(iterator.next());
}
is essentially the same as
List<String> strings = new LinkedList<>(Arrays.asList("first", "second"));
for (String string : strings) {
    System.out.println(string);
}
because the generated byte code for the second code snippet executes the same operations underneath as for the first code snippet. So the for-each loop, introduced with Java 5 is merely syntactic sugar for the for loop that explicitly deals with an iterator.

However this C-style for loop works with an index
List<String> strings = new LinkedList<>(Arrays.asList("first", "second"));
for(int index = 0; index < strings.size(); index++) { 
    System.out.println(strings.get(index));
}
and uses #get(index) instead of iterator.next(). This has vast implications on the execution performance of this loop. Both former loops call iterator.next() which is an O(1) operation, making the both loops to O(n) operations whereas strings.get(index) is an O(n) operation, making the entire loop an O(n²) operation which is substantially slower.

The first and last loop can be both expressed using the for-each' syntactic sugar form.