List implementations: does LinkedList really perform so poorly vs. ArrayList and TreeList?

Viewed 10552

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.

6 Answers
Related