Why looping an Add operations in LinkedList takes longer than ArrayList?

Question

So I know that LinkedList should be much faster (compared to ArrayList) when the main operation is add as it doesn't need to copy the array that runs out of empty slots.

As stated here :

Another benefit of using a LinkedList arise when you add or remove from the head of the list, since those operations are O(1), while they are O(n) for ArrayList.

So I created this small program to benchmark it. To my surprise, it turned the other way around, so the ArrayList is faster. Which seems counterintuitive.

I'm not sure what I'm missing here:

    public static void main(String[] args) {

    for (int i = 1000; i < 100000000; i *=5) {
        System.out.println(" - - - - ");
        System.out.println("size " + NumberFormat.getNumberInstance(Locale.US).format(i));
        List<Integer> list = new ArrayList<>();
        populateList(list, i);
        list = null;

        List<Integer>list2 = new LinkedList<>();
        populateList(list2, i);
    }

}

private static void populateList(List<Integer> list, long size) {
    long start = System.currentTimeMillis();
    for (int i = 0; i < size; i++) {
        list.add(i);
    }
    long after = System.currentTimeMillis();
    System.out.println(list.getClass().getCanonicalName() + " Diff: " + (after - start));
}

And the output is:

---

size 1,000

java.util.ArrayList Diff: 0

java.util.LinkedList Diff: 0

---

size 5,000

java.util.ArrayList Diff: 1

java.util.LinkedList Diff: 0

---

size 25,000

java.util.ArrayList Diff: 3

java.util.LinkedList Diff: 2

---

size 125,000

java.util.ArrayList Diff: 5

java.util.LinkedList Diff: 4

---

size 625,000

java.util.ArrayList Diff: 20

java.util.LinkedList Diff: 13

---

size 3,125,000

java.util.ArrayList Diff: 104

java.util.LinkedList Diff: 1254

---

size 15,625,000

java.util.ArrayList Diff: 3274

java.util.LinkedList Diff: 4490

---

size 78,125,000

java.util.ArrayList Diff: 14457

java.util.LinkedList Diff: 88370

Answer 1

You are inserting to the end of list for which both ArrayList and LinkedList are O(1) as the LinkedList implementation is a doubly-linked list which has a tail pointer as well.

To insert at the head, pass the index as well.

list.add(0, i);

Also see: How do I write a correct micro-benchmark in Java?