2

I know that iterating through a LinkedList using

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

to get the single objects has bad performance as each call of .get(i) iterates from the beginning of the list up to i.

The correct way would be using an Iterator. So far so good.

But what about this style:

for(Item item : list){
  // item is already here
}

Does this have the same performance like using Iterators? How does this work internally?

Smashnet
  • 45
  • 5
  • You could implement a LinkedList which has no bad performance using an old style loop and list.get(i). Simply cache the last node accessed in hope that the next call is the directly following node in the list. This would result in a similar performance like any iterator usage. – MrSmith42 Feb 23 '13 at 19:23
  • possible duplicate of [How does the Java for each loop work?](http://stackoverflow.com/questions/85190/how-does-the-java-for-each-loop-work) – Brian Roach Feb 23 '13 at 19:34

3 Answers3

3

Does this have the same performance like using Iterators?

Yes. Both variants generate the same bytecode. The following byte code was generated from a for-each-loop, but when using an iterator in the loop it looks exactly the same:

for(Object o : list) {
}

  44: aload_1
  45: invokevirtual #30                 // Method java/util/LinkedList.iterator:()Ljava/util/Iterator;
  48: astore_3
  49: goto          59
  52: aload_3
  53: invokeinterface #34,  1           // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
  58: astore_2
  59: aload_3
  60: invokeinterface #40,  1           // InterfaceMethod java/util/Iterator.hasNext:()Z
  65: ifne          52

How does this work internally?

In case of non-arrays, the for-each-loop uses Iterators internally. See the byte code above - all the methods are invoked which would also be invoked when using an Iterator.

See also The For-Each Loop and How does the Java 'for each' loop work? for some additional information.

Community
  • 1
  • 1
Andreas Fester
  • 36,091
  • 7
  • 95
  • 123
2

The foreach loop uses the Iterable interface. It calls iterator() and than iterates with the iterator. A special handling is used for arrays.

MrSmith42
  • 9,961
  • 6
  • 38
  • 49
0

One difference is for each loop is use when you don't want to change the size of the list. because it uses iterators which become invalidate after resize of the list.Whereas it's not a case in normal for loop.But the standard loop make a call to size function each time which make it less efficient then for each. To get the same performance of both you need to put the constant value like 10,15,..etc in condition of standard loop.

  • For Each -- Read only mode

  • Standard For -- Read Write Both

Specific to the Question : the standard for loop is really inefficient because you have to traverse the list each time you call the get from the beginning.This is more problematic then the call of size

Arpit
  • 12,767
  • 3
  • 27
  • 40
  • The call to `size()` is not the inefficient part of the traditional `for` loop with a `LinkedList`, it's the `get(i)` call that makes it slow. `get(i)` internally iterates from the first to `i` on every call, whereas the iterator remembers it's current position and gets to the next element in a single step. – jlordo Feb 23 '13 at 19:29
  • Ya that's true but i'm talking only in general for difference. – Arpit Feb 23 '13 at 19:32
  • OPs question is clearly about `LinkedList`. A general `List` answer doesn't seem to helpful. Your statement that using a constant value instead of `size()` to get the same performance is plain wrong because of how `LinkedList` is implemented. – jlordo Feb 23 '13 at 19:34