Performance benchmark for ArrayList and LinkedList in java

Question

After reading this [question]: When to use LinkedList over ArrayList? I tried to benchmark the performance of ArrayList and LinkedList. But the result I found out is very different from the answer. ArrayList performance is 2-3 time better than LinkedList as far as add() is concerned. As far I know LinkedList.add(E element) is O(1) <--- main benefit of LinkedList ArrayList.add(E element) is O(n - index) But the result show that Array list is much faster than LinkedList

Can anyone please explain this behaviour

 public static void main(String[] args) {
    long start = System.currentTimeMillis();
    List<Integer> b = new LinkedList<Integer>();
    for (int i = 0; i < 1000000; i++) {
        b.add(i);
    }
    System.out.println(System.currentTimeMillis() - start);

    start = System.currentTimeMillis();
    List<Integer> a = new ArrayList<Integer>();
    for (int i = 0; i < 1000000; i++) {
        a.add(i);
    }
    System.out.println(System.currentTimeMillis() - start);

}

See http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java — leventov, Mar 11 '14 at 13:08

JB Nizet · Answer 1 · 2014-03-11T09:54:40.973

You're confused. Adding an element at the end of a List is O(1) is both lists.

The only exceptional case with ArrayList is when the capacity of the list has been reached, which forces ArrayList to instantiate a new array and copy all the elements from the old one to the new one. But this happens rarely because the capacity is multiplied by 1.5 every time it's done.

Adding an element in the middle of the list is O(N) in both cases. The LinkedList must iterate (from the start of from the end) until it find the location where the new node must be inserted. The ArrayList must shift all the elements from the insertion index to the end.

score 0 · Answer 2 · answered Mar 11 '14 at 09:54

You are only testing the append property of a list.

ArrayList and LinkedList are concrete implementation of a list. At the end of the day your benchmark purpose is to determine which kind of list is more appropriate for which situation. That's why a valid benchmark would try to test both implementation against all the new operations and stipulations provided by the List interface.

Performance benchmark for ArrayList and LinkedList in java

2 Answers2