Comparing the two methods get() of ArrayList and next() of LinkedList, it seems that get() is faster and simplier. Adding to Thomas's answer: here's a typical ranking of the speeds of these methods:
ArrayList's get()LinkedList's Iterator's hasNext() + next()ArrayList's Iterator's hasNext() + next()LinkedList's get() The thing to realize here is that the relative differences between the first three just aren't that big most of the time, and the time required is roughly proprtional to the size of the collection - as you'd expect, you can't really get better than O(n) performance for looping though an entire collection.
By contrast, LinkedList's get() can be
much, MUCH worse than Tom's statistics show, as it's ultimately an O(n^2) to loop through the whole list. Here are some results I got for various collection sizes:
Note that my results are a bit different from Tom's. The difference between iterating a LinkedList and doing get() on an ArrayList doesn't really show a clear winner - maybe the ArrayList get() is faster on average, but not by much, and not always. And the ArrayList iteration is only a little slower. It's the LinkedList get() that stands out. ("********" means "Jim got tired of waiting".) It doesn't really matter much which of the other three you use, as long as you never use LinkedList's get() on any sizable collection.
Looking at Tom's results, I'm not sure why there isn't a bigger difference shown for LinkedList's get(). My guess is that when he says 50000 repetitions, the collection size is much much smaller - he just repeats the
test 50000 times to (hopefully) eliminate JIT startup effects and other sources of error. In contrast, where I say size = 40000, that's a collection with 40000 elements, which I iterate through exactly once. My results were obtained using J2SDK 1.4.2 on a 500 MHz P3 with way to much memory for a processor from the previous milennium.
Here's the code (just change which lines are commented out):
Note that the sum variable is just there to ensure that the JIT can't optimize all the calls out of existence (since otherwise they don't really
do anything). Though you can comment it out with relatively little effect it seems. It adds a bit to the total time for each of this methods, but does little to the relative standings, as each test has that same overhead...
[ August 17, 2003: Message edited by: Jim Yingst ]