This post originated from an RSS feed registered with Java Buzz
by dion.
Original Post: When to use LinkedList? Never?
Feed Title: techno.blog(Dion)
Feed URL: http://feeds.feedburner.com/dion
Feed Description: blogging about life the universe and everything tech
An interesting statement is this: "ArrayList is faster than LinkedList, except when you remove an element from the middle of the list." I have heard this on more than one occasion, and a few months ago, decided to try out how true that statement really was.
How many Java developers actually test the affect that a particular collection type would have on the performance? I would be willing ~0.01%.
Heinz goes on to benchmark both lists working at the beginning, middle, and end of sample lists:
beginning ArrayList took 4346
beginning LinkedList took 0
middle ArrayList took 2104
middle LinkedList took 26728
end ArrayList took 731
end LinkedList took 1242
And the conclusion is hilarious:
So, when should you use LinkedList? For a long list that works as a FIFO queue, the LinkedList should be faster than the ArrayList. However, even faster is the ArrayBlockingQueue or the CircularArrayList that I wrote a few years ago. The answer is probably "never".
A cool tool would be one that goes through and tests various Lists in your live code. AOP could wrap around the creation and inject different versions ;)
Of course, this would only be used AFTER we found that the Collection was a bottleneck. Who would optimize prematurely? :)
Previous Topic
