CODEWITHSUNDEEP
javaperformancelistarraylistlinked-list
AlessioG
AlessioG

Reputation: 604

Time comparison of add method for: ArrayList, LinkedList, ArrayList (initialized with some value)

I wish to know more about data structure and about their implementations (in JAVA language). Today I wrote a test to compare (time comparison) different implementations of the ADT List. Specifically I compared add method, here's my test:

@Test
public void testTime() {
    long i = 10000000;
    long INITIALIZED_VALUE=5000000;
    List<Integer> arrayBasedList = new ArrayList<Integer>();
    List<Integer> linkedBasedList = new LinkedList<Integer>();
    List<Integer> arrayBasedInitialedSizeList = new ArrayList<Integer> (INITIALIZED_VALUE);

    long t1 = System.currentTimeMillis();
    for (int index = 0; index <= i; index++) {
        arrayBasedList.add(index);
    }
    long t1End = System.currentTimeMillis() - t1;

    long t2 = System.currentTimeMillis();

    for (int index = 0; index <= i; index++) {
        linkedBasedList.add(index);
    }
    long t2End = System.currentTimeMillis() - t2;

    long t3 = System.currentTimeMillis();
    for (int index = 0; index <= i; index++) {
        arrayBasedInitialedSizeList.add(index);
    }
    long t3End = System.currentTimeMillis() - t3;

    System.out.println("ArrayBased: " + t1End);
    System.out.println("LinkedList:" + t2End);
    System.out.println("ArrayBasedInitializedSize: " + t3End);

    System.out.println("End");
}

And I obtained this result:

ArrayBased: 5681 LinkedList:12830 ArrayBasedInitializedSize: 858

Why LinkedList is slower than ArrayList implementation? I thought that add method, for LinkedList implementation, was faster than add method for Array implementation.

Anyone can explain me why array is faster than linkedlist for the add method?

Thanks

Alessio

Upvotes: 0

Views: 2411

Answers (3)

leventov
leventov

Reputation: 15283

In short: add operation on ArrayList is faster than on LinkedList because it involves (read, write, update) less memory locations:

  • ArrayList: update int size field, read Object[] elements field, read elements.length, write to elements at index.

  • LinkedList: update int size field, update Entry tail field, allocate new Entry, write to the new entry's prev and element fields, write tail.next field.

More precise timings:

@GenerateMicroBenchmark
public int arrayList_add() {
    List<Object> list = new ArrayList<>(1000);
    Object x = new Object();
    for (int i = 0; i < 1000; i++) {
        list.add(x);
    }
    return list.size();
}

@GenerateMicroBenchmark
public int linkedList_add() {
    List<Object> list = new LinkedList<>();
    Object x = new Object();
    for (int i = 0; i < 1000; i++) {
        list.add(x);
    }
    return list.size();

Results:

Benchmark             Mean   Mean error    Units
arrayList_add        5,234        0,019  usec/op
linkedList_add       6,417        0,032  usec/op

Upvotes: 1

Tim B
Tim B

Reputation: 41188

There are two things here.

The first is that your timings are unreliable as you haven't "warmed up" the code before each run. Java optimizes and compiles code as it is run so the first few times through it are much slower than later runs. You should run through your test loops a few hundred times, throw those results away and then do the timings.

To answer the question though:

LinkedList is constant time no matter how long the list is but on each add it has to do a lot more work. It needs to create the wrapper object, insert it into the list, update references, etc.

On the other hand ArrayList just sets a value into the array and then increments the size counter. Only if it needs to re-allocate the array does it then have to do a lot of work.

Do the test adding new objects at the start and compare the results though and you will see things swing more back in the favor of linked lists as now ArrayList needs to shuffle up all the values every time.

The cost to reallocate the arrays is also illustrated with your third test, by knowing the size in advance the ArrayList becomes even more efficient.

Big O notation is helpful when discussing algorithms, but you need to understand what it actually means or it can be very misleading. It's talking about the Order of the operation, not how long it actually takes. ArrayList and LinkedList are both O(1) for most append insertions, ArrayList insertion is O(n) if it needs to reallocate.

All O(1) says is that it still takes the same amount of time no matter how many objects are in the list. Add something to the end of a 10 item list, 100 item list, 10000 item list it still takes the same time.

LinkedList though takes more time than ArrayList does - even though they still have the same O(1) order.

In fact the speed difference is such that even if you look at adding to the start of the list where LinkedList is O(1) and ArrayList is O(n) ArrayList is still faster for small lists!

To give some idea (this is just an example, don't try and take exact timings out of this!) then if the time taken to add for a LinkedList is L and the time for an ArrayList is A then the total time to do an add at the end is L*1, A*1. To add at the start is L*1, A*N.

So if L/A < N then its actually faster to use an ArrayList even though just looking at the O characteristics you might think you are better using the LinkedList.

(Linked list is also O(n) if you need random access reads, which can be a big factor too).

Upvotes: 4

sas4eka
sas4eka

Reputation: 1

I was surprised by your results and tried to run your code by myself. Here is my output:

ArrayBased: 5589
LinkedList:1219
ArrayBasedInitializedSize: 789
End

As I think, LinkedList's add method should work just a little bit slower than ArrayList (both O(1), but with different constant). They both create new Integer objects and ArrayList just puts them in the array, while LinkedList creates links.

The difference between ArrayBased and ArrayBasedInitializedSize is obvious: array reallocation and elements copying take too much time.

Upvotes: 0

Related Questions