Inserting at the Front of Each, a Thousand Times

The same two lists, and the operation the other one is bad at: adding at position zero, over and over.

java

for (int i = 0; i < 1000; i++) {
    array.add(0, i);
}

for (int i = 0; i < 1000; i++) {
    linked.addFirst(i);
}

array.add(0, i) has to make room. Every element already in the list moves up one slot, so the thousandth insert moves nine hundred and ninety-nine elements, and the loop does about half a million moves.

linked.addFirst(i) makes a node and changes two pointers. It costs the same whether the list holds ten elements or ten million, so the loop does about a thousand steps.

Put this beside the positional read and the shared fact comes out: neither list is faster, and the operation you do most decides which one wins. One loop was quadratic on the array list and linear on the linked one; the other was exactly the reverse, with the same interface in both.