Which of these methods is most effective when I traverse a List?

Question

List<T> list = new ArrayList<T>();

1 method:

for(int i = list.length - 1; i >= 0; i--) {
  System.out.println(list.get(i));
}

2 method:

for(T t : list) {
  System.out.println(t);
}

3 method:

Iterator<T> it = list.iterator();     
while(it.hasNext()) {
  System.out.println(it.next());
}

Answer 1

The efficiency is unlikely to be significant - certainly System.out.println is much more likely to be the bottleneck in your particular example.

The second approach (enhanced for loop) is the most readable however. Note that the three approaches don't do the same thing - the first one will iterate from the end rather than the start. Getting the right behaviour almost always trumps running a teeny, tiny bit faster. The more readable your code is, the more likely you are to get it right.

Go for readability, measure the performance of your app, and if it becomes a problem, micro-optimise the bottlenecks (continuing to measure at every step).

EDIT: I was basing this answer on the first line of the question, showing an ArrayList<T> being used.

If you want an answer for any List<T> then there simply isn't an accurate answer. List<T> doesn't offer any guarantees about complexity. It doesn't say how fast you should expect get to be, nor how fast you should expect an iterator to be. You could be using an implementation which has good random access, but a painfully slow iterator. It's unlikely, but it would still be a valid List<T>.

In short: if you're concerned about the efficiency, you need to know what kind of list you're using. In general iterating it likely to be reasonably efficient, and random access may or may not be efficient. (It may be more efficient than iterating, but it's unlikely to be significantly more efficient.) In practice, my experience is that in most applications you actually have enough knowledge to make a reasonable judgement... but I'd still usually code for readability first.

As others have pointed out, if you do want to use random access to get at the elements, then it would be worth ensuring that your list implements the RandomAccess interface too.

Answer 2

I would prefer method 2, unless you need to call something on the iterator object (like iterator.remove()) in which case I would prefer method 3.

The only case I would use method 1 is if I needed to keep a track of the indexes in the loop anyway (and then only in the case of a List that is a dense array-like implentation, like ArrayList).

Update: In line with comments/other answers, I now prefer ListIterator when iterating through a List keeping track of indexes. Leaving method 1 only useful for something that cannot be achieved through any of the other means.

Answer 3

I found this comparison perhaps it helps you forward

Answer 4

The first method will be much slower if you have a long list without random access support. E.g. calling get(1000000) on a LinkedList will have to loop through 1000000 elements from the beginning of the list to reach the 1000000th element. The second and third methods ought to be equivalent.

If it's relevant in your case, List implementations which offer constant time random access to its elements should imlement the java.util.RandomAccess marker interface. At least the List implementations in the standard API do.

Answer 5

Many factors will influence the measure.

First of all, notice that your second and third alternatives are bytecode-equivalent. Indeed, the Java enhanced for loop is a syntactic sugar, which means that, in your case, the second alternative will look, after compilation, exactly like your third alternative.

The most obvious one is the chosen implementation. If you do this test with LinkedList rather than with ArrayList, you'll find that, obviously, iterators are faster than random array access. You'll even find, under some conditions, that iterating over a LinkedList is faster than iterating over an ArrayList.And you now what ? In most of your code, you'll swap with no reason from one to the other impplemenation.

As a consequence, as a general rule of thumb, for both readability and code efficiency, I tend to always use the second method.

Answer 6

On RandomAccess

java.util.ArrayList implements RandomAccess. The documentation is clear on what this means:

Marker interface used by List implementations to indicate that they support fast (generally constant time) random access. [...] As a rule of thumb, a List implementation should implement this interface if, for typical instances of the class, this loop:

for (int i=0, n=list.size(); i < n; i++)
     list.get(i);

runs faster than this loop:

for (Iterator i=list.iterator(); i.hasNext(); )
     i.next();

Thus, for a List that properly implements RandomAccess, the indexed-get is faster.

Note however that this is NOT true for, say, a LinkedList, in which the above code exhibits quadratic performance. This is because LinkedList does not permit constant-time random access; that is, get is linear for LinkedList.

Note that even if the indexed-get is faster, it'll only be by a constant factor. Profile first to see if this optimization attempt is worth it.

Related questions

• When to use LinkedList over ArrayList?

---

On for-each vs Iterator loop

There is no significant difference between the performance of these two constructs that you should concern yourself with. The for-each loop is much more readable but is applicable in more limited scenarios, and thus precisely in those scenarios is where you should use them. When the for-each loop is not applicable, then use an Iterator loop.

A quote from Effective Java 2nd Edition, Item 46: Prefer for-each loops to traditional for loops:

The for-each loop, introduced in release 1.5, gets rid of the clutter and the opportunity for error by hiding the iterator or index variable completely. The resulting idiom applies equally to collections and arrays:

// The preferred idiom for iterating over collections and arrays
for (Element e : elements) {
    doSomething(e);
}

When you see the colon (:), read it as "in." Thus, the loop above reads as "for each element e in elements." Note that there is no performance penalty for using the for-each loop, even for arrays. In fact, it may offer a slight performance advantage over an ordinary for loop in some circumstances, as it computes the limit of the array index only once.

See also

• Java Language Guide/for-each loop

Related questions

• Java foreach efficiency
• Performance difference between Iterator Class and foreach construct
• Performance: Iterating through a List in Java
• traditional for loop vs Iterator in Java
• Is there a performance difference between a for loop and a for-each loop?

Answer 7

Method 1 is very unlikely to be the best one as it has no readability or performance advantage over the others.

If you want to keep track of the index, consider using a ListIterator instead of an Iterator, e.g.

ListIterator<T> it = list.listIterator();
while (it.hasNext()) {
    T t = it.next;
    int index = it.previousIndex();
    System.out.printf("%d => %s%n", index, t);
}

As others have pointed out, method 3 is equivalent to method 2 unless you want to remove elements from the list during iteration.

If profiling shows that the list's get(int) method or the iterator's next() or hasNext() is a performance bottleneck (very rare but it can happen), consider replacing the list with an array (you can still use the for-each syntax, similar to method 2.)

Answer 8

Since there's no explanation on what exactly is meant by effectiveness, I will answer from the position of what should be preferred.

I would prefer the 2nd method as the most readable.

Why: until the program is written, you don't know, where the bottlenecks are going to be. This is why premature optimization is unlikely to yield substantial results. But readability of the code is always relevant, so I would choose the second variant.