Taken from the Apache TreeList
doc:
The following relative performance statistics are indicative of this class:
get add insert iterate remove TreeList 3 5 1 2 1 ArrayList 1 1 40 1 40 LinkedList 5800 1 350 2 325
It goes on to say:
LinkedList
is rarely a good choice of implementation.TreeList
is almost always a good replacement for it, although it does use sligtly more memory.
My questions are:
What is with the ArrayList
add
,
insert
, and remove
times crushing
LinkedList
? Should we expect, for
one, that real-world insertion and removal cases
greatly favor ArrayList
?
Does this TreeList
simply put the nail in the coffin of the venerable LinkedList
?
I am tempted to conclude they have amortized or ignored ArrayList
's growing pains, and have not taken into consideration the insertion and removal times for an item in a LinkedList
that has already been located.
The key thing here is the complexity of insert/delete operations in the three List implementations. ArrayList has O(n) insert/delete times for arbitrary indices, but it is O(1) if the operation is at the end of the list. ArrayList also has the convenience of O(1) access for any location. LinkedList is similarly O(n), but is O(1) for operations at either end of the List (start and end) and O(n) access for arbitrary positions. TreeList has O(logn) complexity for all operations at any position.
This clearly shows that TreeList is faster for large enough Lists as far as insert/deletes in arbitrary positions are concerned. But AFAIK, TreeLists are implemented as a binary search tree, and has a much bigger constant associated with its O(logn) operations than similar operations with ArrayLists which are simply wrappers around an array. This makes TreeList actually slower for small Lists. Also, if all you are doing is appending element into a List, the O(1) performance of ArrayList/LinkedList is clearly faster. Moreover, often the number of insert/deletes are much fewer than the numbers of accesses, which tends to make ArrayList faster overall for many cases. LinkedList's constant time insert/delete at the either end of the List makes it much faster at implementing data structures like Queues, Stacks and Deques.
At the end of the day, it all depends on what exactly you need a List for. There isn't a one-size-fits-all solution. You have to select the implementation most suitable for your job.