Sunday, June 15, 2008

What is faster - ArrayList or LinkedList

Inspired by JavaSpecialists article by Dr. Heinz M. Kabutz of the same title, I decided to verify one aspect where I expected LinkedList to be faster - creation of short-lived collection of items to process a few instructions later.

Say, as in code below:
List store = new (Array|Linked)List();
for (Object o : someData) {
if (condition(o)) {
store.add(new Adapter(o));
}
}
doStuff(store);

I extended Dr. Kabutz' code with following methods (see the original post for context):
public static void testListCreate(List list) {
long time = System.currentTimeMillis();
for (int i = 0; i < NUM_ELEMENTS; i++) {
list.add(new Object());
}
time = System.currentTimeMillis() - time;
System.out.println("Creating " +
list.getClass().getSimpleName() + " took " + time);
}

public static void testListIterate(List list) {
long time = System.currentTimeMillis();
for (Object o : list) {
if (o == null) {
throw new NullPointerException();
}
}
time = System.currentTimeMillis() - time;
System.out.println("Iterating " +
list.getClass().getSimpleName() + " took " + time);
}


Called from main test method:
testListCreate(new ArrayList());
testListCreate(new LinkedList());
testListCreate(new ArrayList(NUM_ELEMENTS));

testListIterate(ar);
testListIterate(new LinkedList(ar));


The results were quite surprising (Mac OS X 10.5.3, JDK1.5 server mode, Intel Core 2 Duo 2.4GHz):
Creating ArrayList took 31
Creating LinkedList took 50
Creating ArrayList took 9
Iterating ArrayList took 8
Iterating LinkedList took 2
beginning ArrayList took 1839
beginning LinkedList took 3
middle ArrayList took 976
middle LinkedList took 3920
end ArrayList took 446
end LinkedList took 768


For small arrays the results and differences were negligible.

Conclusions (random relevance to the subject):
- I have a faster computer then Mr Kabutz ;-)
- ArrayList creation is faster, even when the initial list size is unspecified.
- Iteration of LinkedList is faster, but not faster enough to pay off the creation overhead.
- ArrayList comes as a first autocomplete suggestion for 'List l = new [Ctrl-Shift-Space]', so it is much easier to pick than any other List implementation.
- There are lies, damns lies, statistics and microbenchmarks.
- blogger.com is sub-optimal for writing posts about java code.

2 comments:

  1. Maciek Gorywoda30 June, 2008 15:09

    Iteration of LinkedList is faster, but not faster enough to pay off the creation overhead.

    So if I have a poll for unused, already created (Array|Linked)Lists then a LinkedList is a better choice?
    Damn, I always took it for granted that ArrayList is faster...

    ReplyDelete
  2. By "creation" I meant populating - having an already created LinkedList would not help.

    I always thought that LinkedList would be faster to populate, and I was wrong.

    ReplyDelete