ArrayList contains() and LinkedList get() gets slower

Its very important to realize when to use what kind of data structure. It is important to understand how similar data structures differ while performing same operations. For e.g. a List interface is implemented by LinkedList as well as the ArrayList, but they widely differ in terms of the implementation. Due to the different practical scenarios, it is often required to use different implementations for the same interface. One should be very careful in choosing the right implementaion for his use.


While debugging a problem in a real system, I realized that the system was much slower in a particular usecase.


The characteristic of the application was as below :


1. The application created say 1 million objects, sequentially one after another per day.

2. A linked list was used as a window to access (say top n) this huge number of objects.

3. The linked list window was of fix size and represented the latest produced objects.


The use case was to access this list and compute some real time numbers for applications use. This is how the list was used.

int sum = 0;
for(int i=0; i
  Object obj = list.get(i);
  sum = sum + obj.value();
}
// sum was used further by the application.

Initially, this may look like a simple case, which would not have any problem. But this is a big performance problem with LinkedList. Well this may also seem to be a very trivial problem to many, but its a very natural programming error which could happen.

This problem may not be visible if the list is short, or if the list is an ArrayList, but here in this case, it was a LinkedList and problem accentuated only with larger set of data. Below is the code Listing from java.util.LinkedList.

Listing 1.

public E get(int index) {
        return entry(index).element;
    }

private Entry entry(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+size);
        Entry e = header;
        if (index < (size >> 1)) {
            for (int i = 0; i <= index; i++)
                e = e.next;
        } else {
            for (int i = size; i > index; i--)
                e = e.previous;
        }
        return e;
    }

As you can see, in order to get an element at index i, the LinkedList has to iterate over all its elements till it reaches the element at location i.

With the ArrayList, the implementation is different. ArrayList maintains an object array to store its content. Whenever an object is requested at the given index, it just has to get it from this object array. This operation is fast and constant with number of objects in terms of time.

The problem with the LinkedList increases with the number of objects and depends on the location of the object in the list. Below is a test program which I wrote just to get some approximate figures of this slowness.

Listing 2.

int marker = 1000000;
List list = new LinkedList();
Date startDate = new Date();
for (int i = 0; i < 6000000; ++i) {
    list.add(i);
    if (i % marker == 0) {
    Date endDate = new Date();
    System.out.println("put " + (i / marker) + "  " + (endDate.getTime() - startDate.getTime()));
    startDate = endDate;
    }
}
startDate = new Date();
marker = marker / 100;
for (int i = 0; i < 6000000; ++i) {
    list.get(i);
    if (i % marker == 0) {
    Date endDate = new Date();
    System.out.println("get " + (i / marker) + "  " + (endDate.getTime() - startDate.getTime()));
    startDate = endDate;
    }
}

I ran the program and plotted the number of get calls against the time taken as shown below :

Here you can see that initially the curve is steep and then its almost at a slope of 1, which is kinda expected. The idea to take away is that the time taken to search an element in the linked list, in the worse case, linearly increases with the number of elements presnet in the list.

When the list implementation is replaced with ArrayList, then the get calls are not even noticable and time difference you get in the loops is 0 milli seconds.  Against the huge numbers we get in case of the LinkedList.

However the same problem occurs with ArrayList when its method contains() is used. The method contains() have the similar implementation as LinkedList's get() method. Hence its very important and useful to know the complete detailed implementation of the datastructure, before using it.