Home of The JavaSpecialists' Newsletter

111What is faster - LinkedList of ArrayList?

Posted: 2005-07-12Category: PerformanceJava Version: 1.2+Dr. Heinz M. Kabutz
 

Abstract: 

 

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. I know this has nothing to do with Java, but it does concern us as human beings.

Birthday and Anniversary Special: Since the 30th November 2017 is the 17th anniversary of our newsletter and my birthday is coming up on the 4th December, we are giving away a 30% discount on our new Data Structures for Java 9 Course (Late 2017 Edition). Whether you are a seasoned Java programmer or you just want to get ready for your next job interview, this course will help you. Besides detailed lectures, the course has over 130 questions that will help you discover what you missed.

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

 

Related Articles

Browse the Newsletter Archive

About the Author

demo

Java Champion, author of the Javaspecialists Newsletter, conference speaking regular... About Heinz

Java Training

We deliver relevant courses, by top Java developers to produce more resourceful and efficient programmers within their organisations.

Java Consulting

Nobody ever wants to call a Java performance consultant, but with first-hand experience repairing and improving commercial Java applications - JavaSpecialists are a good place to start...

Threading Emergency?

If your system is down, we will review it for 15 minutes and give you our findings for just 1 € without any obligation.