|
Which is Faster - LinkedList
or ArrayList?
This article compares LinkedList and ArrayList and
describes which is faster with an example.
2005-07-12 The Java Specialists' Newsletter [Issue 111] -
What is faster - LinkedList of
ArrayList?
Author:
Dr. Heinz M. Kabutz JDK version: Sun JDK 1.2 - 5.0
If you are reading this, and have not subscribed,
please consider doing it now by going to our subscribe
page. You can subscribe either via email or RSS.
Welcome to the 111th edition of The Java(tm) Specialists' Newsletter. After a quick visit
home to Cape Town, I am yet again in Johannesburg, this time
to present some courses on Design
Patterns.
The old archive page was getting a bit difficult to navigate,
so I have upgraded the structure of my website somewhat, and
put all the newsletters into categories. You can view the
new structure by going to the archive
page. I hope this will make it easier for you :)
I was deeply disturbed this morning by a newspaper
article reporting that since 2003, there have been an additional
estimated 700'000 cases of HIV/AIDS infection in South Africa
alone, bringing the number of people living with HIV/AIDS, to
over 6.2 million. Women between 25 - 29 years of age are
hardest hit, with a 40% infection rate. Please
send me an email if this also concerns you and let us
start a workgroup to see if there is anything we can do as a
Java community to contribute towards slowing this down. I
know this has nothing to do with Java, but it does concern us
as human beings.
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
P.S. we are running a Java 2 Standard Edition course from the
1st to the 5th of August in Cape Town, and we still have one
or two spaces open for anyone in your company that needs to
be trained in Java. These courses can also be run on demand
within your organisation. Please refer to our
website for more information.
This material from
The Java(tm) Specialists' Newsletter by Maximum Solutions (South Africa). Please
contact Maximum Solutions for
more information.
|