I liked reading the Java Specialists’ Newsletter from Heinz.
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? :)
July 13th, 2005 at 6:38 am
If you look in java.util.Collections (the utility class), there’s a set of constants where it switches over algorithms between index-based and iterator-based for non-RandomAccess lists. It’s interesting to see how large some of those numbers are, particularly with the low cost of memory allocation for the iterator.
July 13th, 2005 at 6:57 am
Well, the test case only tests the “best-case” for arraylists, since it removes the element immediately after the insert.
if you try the same test case just with adds only (and wrap the ‘ar’ variable into new ArrayList(ar) before passing it to the test methods), you’ll get quite a different results:
beginning ArrayList took 1252
beginning LinkedList took 10
middle ArrayList took 751
middle LinkedList took 2474
end ArrayList took 0
end LinkedList took 0
The problem with ArrayList at the beginning and end is that it has to System.arraycopy the remainder of the list and possibly allocate new array for the elements if the existing array is not big enough for the elements. Adding to middle of linked list is slow because it has to iterate to the given position.
July 13th, 2005 at 7:08 am
so all in all:
add(i, object) is O(n) for both ArrayList and LinkedList in the worstcase. O(1) for the best case (last position for ArrayList or last & first positions for LinkedList).
get(i) is O(1) for ArrayList and O(n) for LinkedList. So conclutions ? Well, choosing the list type beforehand is premature optimization I say ;).
July 13th, 2005 at 1:44 pm
See also TreeList in Commons Collections:
http://jakarta.apache.org/commons/collections/apidocs-COLLECTIONS_3_1/org/apache/commons/collections/list/TreeList.html
for a different approach at an ArrayList alternative thats good at insert/remove in the middle.