Meaningless Drivel is fun!*
The moose likes Java in General and the fly likes Question on List.get() in for loop vs listIterator() Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Question on List.get() in for loop vs listIterator()" Watch "Question on List.get() in for loop vs listIterator()" New topic
Author

Question on List.get() in for loop vs listIterator()

Robert Paris
Ranch Hand

Joined: Jul 28, 2002
Posts: 585
Anyone know if it's better performance (and code-maintenance-wsie) to do a for loop and call "get()" to get the elements in a list versus getting the list iterator and doing a "hasNext()" loop?
Barry Gaunt
Ranch Hand

Joined: Aug 03, 2002
Posts: 7729
PS: Whoops, I've answered a more general question than you asked. But I'll leave it in.
From a design point of view: suppose you have Collection c = new ArrayList(); and then you fill the list with stuff. You cannot use c.get() because get() does not exist in Collection. Iterator i = c.iterator(); will work though.
So one point to consider is the amount of generality your program requires. Is it required that the List type is possibly replaced by another Collection type at a later time?
For performance: if you use an ArrayList, say al, then I would guess ( I have not checked it ) that the for( int i = 0, n = al.size() ; i < n ; i++ ) { Object o = al.get( i ); } would be faster than an iterator, because the ArrayList is implemented by means of an array of Object.
You'd best check each Collection type ( API details, source code ) on a case-by-case basis, and compare with your application's specific requirements.
For get() verses ListIterator.next(): if you just want to blast down the list from front to back the for/get would *most likely* perform better than the ListIterator because ListIterator has to maintain more context about its position in the list. However, again check the source.
[ February 02, 2003: Message edited by: Barry Gaunt ]
[ February 02, 2003: Message edited by: Barry Gaunt ]

Ask a Meaningful Question and HowToAskQuestionsOnJavaRanch
Getting someone to think and try something out is much more useful than just telling them the answer.
Peter den Haan
author
Ranch Hand

Joined: Apr 20, 2000
Posts: 3252
Robert,
When all you have is "a List" then there is no question about it: use an Iterator. Because the List you have may be a LinkedList and get() will perform O(n), giving the entire loop O(n*n) performance. Ouch. An Ierator will give you O(n) performance on any flavour of List.
If, on the other hand, you know that your List is actually an ArrayList, it is tempting to use get() is a little bit faster. Do not do this. You would be, deviously, implicitly, coding to implementation rather than interface. Increasing the coupling, and reducing the abstraction and flexibility in your code. If you really, really have to do this (remember the first three rules of optimization though) then use get(), while at the same time changing variables and method signatures from List to ArrayList to clearly flag up that you are coding to a specific implementation here.
Finally, if you can't require an ArrayList, for example because you're developing a library and really can't make assumptions about the kind of List you're getting, yet you still need the fastest possible iteration, useYou may find the javadoc for java.util.RandomAccess interesting reading.
- Peter
[ February 02, 2003: Message edited by: Peter den Haan ]
Barry Gaunt
Ranch Hand

Joined: Aug 03, 2002
Posts: 7729
I said:
For get() verses ListIterator.next(): if you just want to blast down the list from front to back the for/get would *most likely* perform better than the ListIterator because ListIterator has to maintain more context about its position in the list. However, again check the source.

I had to think hard about what Peter has said about get() being of O(n). Of course he's correct in the case of a linked list. Every time you do get(i) the thing's going to start at the head of the list and chug along, following links, until it has got to the i-th item.
In the case of an ArrayList I'm following the advice of Joshua Bloch (Effective Java).
Thanks, Peter for the education
PS The RandomAccess interface approach is interesting!
[ February 02, 2003: Message edited by: Barry Gaunt ]
Robert Paris
Ranch Hand

Joined: Jul 28, 2002
Posts: 585
Thank you both for the answers. Peter - you're 100% right. I'm going back and changing my code to use Iterator. I thought it was a bit cleaner/more decoupled but didn't realize the huge danger of using the for loop.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Question on List.get() in for loop vs listIterator()
 
Similar Threads
ArrayList
for loop and the list iterator
File Directory
Which is better?
Don't understand C++ Iterators and Vectors