ArrayList vs LinkedList when inserting items at random indices?

Question

So I've stumbled across this bit of code and was wondering specifically why it is that the java.util.ArrayList is significantly faster than the java.util.LinkedList.

What the code does is create both an array and linked list and providing each a single element to start out with. The addMoreItems(List<Integer> vals) will then run for both arrays, and for each it will insert a random value at some random index in the array. The amount of values that it will add to each array is determined by the input from the user.

private static int amount = 0;

public static void main(String[] args) {

    Scanner scan = new Scanner(System.in);
    System.out.print("Enter amount of elements to add: ");
    amount = scan.nextInt();

    LinkedList<Integer> linked = new LinkedList<Integer>();
    ArrayList<Integer> array = new ArrayList<Integer>();

    linked.add(0);
    array.add(0);

    // Bench mark linked list speed
    long start = System.nanoTime();
    addMoreItems(linked);
    long end = System.nanoTime() - start;

    // Bench mark array list speed
    long start2 = System.nanoTime();
    addMoreItems(array);
    long end2 = System.nanoTime() - start2;

    System.out.println("Linked list took: " + (end / 1000000.0) + "ms");
    System.out.println("Array list took: " + (end2 / 1000000.0) + "ms");

}

public static void addMoreItems(List<Integer> vals) {

    Random r = new Random();

    for (int i = 0; i < amount; i++)
        vals.add(r.nextInt(vals.size()), r.nextInt());

}

So fundamentally, one would think that the addMoreItems() function would take the same amount of time to return for both list types (maybe the LinkedList would be slightly faster). However, the actual result seems to indicate that the ArrayList is significantly faster than the linked list regardless of the number of elements you're adding (you can try it out here).

Anyways, my guess is that it may have to do with caching and maybe the fact that the LinkedList will allocate memory for each individual element that is inserted, whereas the ArrayList will allocate blocks of memory to reduce the number of allocations.

Why is the ArrayList faster?

Regarding the dupe: inserting in the middle or at random indices don't matter, both approach use the LL in an ineffective way. — Tom, Nov 06 '19 at 19:32
When explicitly specifying an index for the insertion, the optimal case for a LinkedList is to add near the start of the list. The optimal case for an ArrayList is to add near the end (though it matters little if it's anywhere in between - copying the elements to a new array with a call to the native `System.arraycopy()` is really fast, even on large arrays). If you bias your test according to that, the LinkedList would actually win out. — Crusha K. Rool, Nov 06 '19 at 19:50

score 2 · Accepted Answer · answered Nov 06 '19 at 19:35

Your expectations were incorrect. The ArrayList Javadoc explicitly says (in part)¹

The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

Because the constant factor is higher each add operation on a LinkedList is slightly slower than on ArrayList, so you should have expected ArrayList to be faster.

_{¹ Added bold for emphasis.}

score 2 · Answer 2 · answered Nov 06 '19 at 19:42

In the case of LinkedList, accessing time of a node is O(n) in the worst case. This is because if you want to access the 4th node of the LinkedList you need to iterate from the head to that particular node.
ArrayList is a combination of arrays and lists. It has the advantage of indexing nodes, and the ability to add more adds if required. In ArrayList, you can access a particular node in constant time, O(1), no iteration is required

ArrayList vs LinkedList when inserting items at random indices?

2 Answers2