What is the best way to iterate over list

Question

I have worked pretty much on collection but I have few doubts.

I am aware that we can iterate list with iterator.

Another way is that we can go through as below:

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

Here I think there is problem that each time it will call list.size() that will build whole tree that will impact performance.

I thought other solution as well like:

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

I think this can solve the problem. I am not much exposed to thread. I am thinking that whetherthis should be right approach or not.

Another way I thought is like:

for (Object obj; list){

}

With this new for loop, I think compiler again checks size of list.

Please give best solution from these or alternative performance efficient approach. Thank you for your help.

Answer 1

Calling size() at each iteration is not really a problem. This operation is O(1) for all the collections I know of: size() simply returns the value of a field of the list, holding its size.

The main problem of the first way is the repeated call to get(i). This operation is O(1) for an ArrayList, but is O(n) for a LinkedList, making the whole iteration O(n²) instead of O(n): get(i) forces the list to start from the first element of the list (or the last one), and to go to the next node until the ith element.

Using an iterator, or using a foreach loop (which internally uses an iterator), guarantees that the most appropriate way of iterating is used, because the iterator knows about how the list is implemented and how best go from one element to the next.

BTW, this is also the only way to iterate through non-indexed collections, like Sets. So you'd better get used to use that kind of loop.

Answer 2

For your example is the best way:

for (Object obj: list){

}

It is the same like in java version < 1.5:

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

It use iterator of collection. You actually don't need the size of collection. The .size() method is should actually don't build the tree, but .get() can loops to the given element. .get() and .size() methods depend on List implementation. .get() In ArrayList should be actually O(1) complexity and not O(n)

UPDATE

In java 8 you can use:

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