Why insertion at the End of the Linked list is slow as compare to Array list

Question

Even though Linked list internally use the Doubly Linked List , So it can easily identify the last element and start adding. Now still it's slow compare to array list why ?

Please refer the below code with output :

package com.collection;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Performance {

    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<Integer>();
        List<Integer> LinkedList = new LinkedList<Integer>();
        checkPerformance("arrayList", arrayList);
        checkPerformance("LinkedList", LinkedList);
    }

    private static void checkPerformance(String type, List<Integer> list) {
        for (int i = 0; i < 1E6; i++) {
        list.add(i);
        }
        long start = System.currentTimeMillis();
        for (int i = 0; i < 1E6; i++) {
            list.add(i);
        }
        long end = System.currentTimeMillis();
        System.out.println("Time Taken" + " " + (end - start)
        + " ms for the type " + type);
    }
}

Output : Time Taken 250 ms for the type arrayList Time Taken 390 ms for the type LinkedList

You should learn how to create proper microbenchmarks, this is not appropriate. Regarding your question: ArrayList has better locality, the changes are amortized. — Gábor Bakos, Feb 22 '14 at 07:54
Running your code I get : "Time Taken 124 ms for the type arrayList Time Taken 18 ms for the type LinkedList." Which is not a mark of support for the validty of your benchmarking technique btw. — NimChimpsky, Feb 22 '14 at 07:55
Also, you benchmark isn't fair with ArrayList: an ArrayList has to recreate a whole new (bigger) array and copy everything from the old array to the new one every time its capacity is exhausted. LinkedList just has to create a Node and append it to the last one. So if you want to only measure the time it takes to add an element, in a typical situation, then initialize the ArrayList with its final size: 1E6. — JB Nizet, Feb 22 '14 at 08:04
It's best for understanding if you verify this yourself, with pen and paper: In practically all situations, `ArrayList` will have allocated and modified *less* total memory than `LinkedList`, for same data. Yes, even just after `ArrayList` has just done reallocation and has half of reserved space unused, its cumulative memory use is still less than allocation and linking overhead suffered by `LinkedList`. The use cases for `LinkedList` in Java are few, and far between. — hyde, Feb 22 '14 at 08:24
...and because these are simple containers, and you are just measuring element adding, then memory use directly correlates with measured time. There's no searching the right place to insert, there's no calculating hashes, or nothing like that, just following pointers and doing addition. — hyde, Feb 22 '14 at 08:29
@JB that's only a reasonable thing to do if you expect to know the final size in "the true system" — Richard Tingle, Feb 22 '14 at 08:47
@RichardTingle: yes, it all depends what you intend to measure. — JB Nizet, Feb 22 '14 at 09:01
Presizing the arraylist results in a quite minor speed advantage. It is mostly not worth it as there is more chance of introducing bugs or off-by-one presizing errors, which will result in worst-case memory overhead. — Marko Topolnik, Mar 03 '14 at 14:11

Florent Bayle · Answer 1 · 2014-02-22T09:33:19.110

So, I think that you assume that ArrayList will be slower because it has to allocate a new array and copy the old array into the new one every time you add an element to it, but it's not the case.

When you add an element to an ArrayList, this element is added to a classical array, but before, it calls the following method to ensure that the backing array is of a sufficient size to add your element:

/**
 * Increases the capacity of this <tt>ArrayList</tt> instance, if
 * necessary, to ensure that it can hold at least the number of elements
 * specified by the minimum capacity argument.
 *
 * @param   minCapacity   the desired minimum capacity
 */
public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3)/2 + 1;
        if (newCapacity < minCapacity)
        newCapacity = minCapacity;
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

What this means is that if the size of the backing array isn't sufficient to add you element, it will not increase the size to oldCapacity + 1 as you can expect, but to (oldCapacity * 3)/2 + 1, to allow you to add more elements to it without having to allocate and copy it again.

At the end of your first loop, the capacity of your array will be 1005308 (you can check it by setting a breakpoint after the loop and inspecting the list variable). So to, add 1000000 more elements, you will re-allocate it only two times: one to go from 1005308 to 1507963 and one to go from 1507963 to 2261945. The rest of the time, you will just set an element in the backing array to another value (it's really cheap).

With the LinkedList, on the other hand, you will have to allocate a new element every time you add something to the list, and you will have more operations (set the value, and change two pointers values), that's why it can take more time than with ArrayList (I tried, and LinkedList was faster for me).

score 1 · Answer 2 · answered Feb 22 '14 at 09:16

Indeed it's completely different for me and every thing is as expected: Time Taken 184 ms for the type arrayList Time Taken 31 ms for the type LinkedList

I even tested this:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class TestClass   {

    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<Integer>();
        List<Integer> LinkedList = new LinkedList<Integer>();
        checkPerformance("arrayList", arrayList);
        checkPerformance("LinkedList", LinkedList);
    }
    private static void checkPerformance(String type, List<Integer> list) {
        for (int i = 0; i < 1E4; i++) {
            list.add(i);
        }
        long start = System.currentTimeMillis();
        for (int i = 0; i < 1E4; i++) {
            list.get(i);
        }
        long end = System.currentTimeMillis();
        System.out.println("Time Taken" + " " + (end - start)
                + " ms for the type " + type);
    }
}

and the results : Time Taken 1 ms for the type arrayList Time Taken 82 ms for the type LinkedList as expected!

Why insertion at the End of the Linked list is slow as compare to Array list

2 Answers2

Related