ExampleDifficulty: Intermediate1 min

ArrayList vs LinkedList Example: Inserting at the Front

The operation the linked list wins, and the array list pays for with every element it holds.

Inserting at the front of a list is where LinkedList beats ArrayList: an ArrayList has to shift every element up one slot, and a LinkedList only changes two pointers. An ArrayList called array and a LinkedList called linked, each adding at the front a thousand times:

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 reading by position, where ArrayList answers at once and LinkedList walks node by node, and the shared point comes out: neither list is faster, and the operation you do most decides which 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.

← → move through sections and cards