What is faster - LinkedList of ArrayList? (Author: Dr. Heinz M. Kabutz)

What is faster - LinkedList of ArrayList?

As programmers, we often try to eke the last ounce of performance out of our collections. 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. Here is some code that I wrote during last week's Java 5 Tiger course:

import java.util.*;

public class ListTest {
private static final int NUM_ELEMENTS = 100 * 1000;
public static void main(String[] args) {
List ar = new ArrayList();
for (int i = 0; i < NUM_ELEMENTS; i++) {
ar.add(i);
}
testListBeginning(ar);
testListBeginning(new LinkedList(ar));
testListMiddle(ar);
testListMiddle(new LinkedList(ar));
testListEnd(ar);
testListEnd(new LinkedList(ar));
}
public static void testListBeginning(List list) {
long time = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
list.add(0, new Object());
list.remove(0);
}
time = System.currentTimeMillis() - time;
System.out.println("beginning " +
list.getClass().getSimpleName() + " took " + time);
}
public static void testListMiddle(List list) {
long time = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
list.add(NUM_ELEMENTS / 2, new Object());
list.remove(NUM_ELEMENTS / 2);
}
time = System.currentTimeMillis() - time;
System.out.println("middle " +
list.getClass().getSimpleName() + " took " + time);
}
public static void testListEnd(List list) {
long time = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
list.add(new Object());
list.remove(NUM_ELEMENTS);
}
time = System.currentTimeMillis() - time;
System.out.println("end " +
list.getClass().getSimpleName() + " took " + time);
}
}


One small little addition in Java 5 is the method getSimpleName() defined inside Class. I do not know how many times I have needed such a method and have had to write it.

The output is obvious, but surprising nevertheless in the extent of the differences:

beginning ArrayList took 4346
beginning LinkedList took 0
middle ArrayList took 2104
middle LinkedList took 26728
end ArrayList took 731
end LinkedList took 1242


Finding the element in the middle of the LinkedList takes so much longer that the benefits of just changing the pointer are lost. So, LinkedList is worse than ArrayList for removing elements in the middle, except perhaps if you are already there (although I have not tested that).

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".

Kind regards

Heinz

Read it all here...