Why LinkedList is slower then ArrayList when adding to the end of list?

Question

I read THIS and

And understood that LinkedList add(E element) is O(1) and ArrayList add(E element) is O(1) amortized, but O(n) worst-case since the array must be resized and copied

But, when i try to check it

public class ArrayListVSLinkeedList {

public ArrayListVSLinkeedList() {

    final int COUNTER = 15000000;

    List<Integer> arrayList = new ArrayList<Integer>();

    long tStart_add = System.currentTimeMillis();

    for (int i = 0; i < COUNTER; i++) {
         arrayList.add(i);
    }
    long tEnd_add = System.currentTimeMillis();
    long tDelta_add = tEnd_add - tStart_add;
    System.out.println("Adding to ArrayList: " +tDelta_add);


    List<Integer> linkedList = new LinkedList<Integer>();
    tStart_add = System.currentTimeMillis();
    for (int i = 0; i < COUNTER; i++) {
        linkedList.add(i);
    }
    tEnd_add = System.currentTimeMillis();
    tDelta_add = tEnd_add - tStart_add;
    System.out.println("Adding to LinkedList: " +tDelta_add);
}

public static void main(String[] args) {
    new ArrayListVSLinkeedList();
}
}

I received at output:

Adding to ArrayList: 9122

Adding to LinkedList: 19859

I know, this is not real benchmark, but... Finally, adding element to the end of ArrayList is faster then to LinkedList. Why this happens?

I would not trust the results of that benchmark. It makes the classic mistakes of not accounting for JVM warmup effects such as JIT compilation, and heap warmup. — Stephen C, Feb 10 '15 at 12:47

score 6 · Accepted Answer · answered Feb 10 '15 at 12:18

This is simply due to the implementation.

Have a look at the implementation of ArrayList.add:

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

An ArrayList internally holds an array whose elements are references to the objects you are managing with that list. The method ensureCapacityInternal simply checks whether this internal array is still large enough to add another element.

If so, the element is added and the method returns. This is extremely fast (and - btw - is O(1)).

If the array is already full, then a new array with a larger size will be allocated, every reference will be copied from the old array to the new array. Afterwards, the element will be added. This - of course - is O(n). But this happens seldom, and because of the resizing strategy (doubling the size) it will become more and more seldom.

On the other hand, let's have a look at the implementation of LinkedList.add:

public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

Here you see that for each added element a new node object must be created which then is added as the last element. No resizing is done, so that method is always O(1), but the creation of a node object takes more time than simply storing a reference.

score 0 · Answer 2 · answered Feb 10 '15 at 12:17

0

Well, it depends how much memory you have on the machine, think that the ArrayList you are creating is already in memory and the LinkedList has to allocate new memory.. Try to run it the other way around and see the results.

Better yet - try to run them in separate methods and see a fair result.

answered Feb 10 '15 at 12:17

DanielM

3,598
5
37
53

Allocating memory in java is not costly (as it is in e.g. C/C++). Creating objects is costly though. – ciamej Feb 10 '15 at 12:32

Why LinkedList is slower then ArrayList when adding to the end of list?

2 Answers2