Alex Rivera | Logout

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

Asked 2009-11-11T05:06:23.910
26

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.

java collections arraylist linked-list treelist
Edit
Report

1 Answer

1

Note that ArrayList is generally faster than LinkedList, even when your code calls just the methods that are constant time for both. For example, ArrayList.add() simplies copies a single variable and increments a counter when no resizing is needed, while LinkedList.add() must also create a node and set multiple pointers. In addition, the LinkedList nodes require more memory, which slows down your application, and garbage collection must deal with the nodes.

If you need to add or remove elements from either end of the list, but don't require random access, an ArrayDeque is faster than than a LinkedList, though it requires Java 6.

A LinkedList make sense for iterating across the list and then adding or removing elements in the middle, but that's an unusual situation.

answered 2009-11-18T07:38:44.690

Your Answer