ArrayList vs LinkedList

Key points

• ArrayList is one contiguous array. LinkedList is a chain of nodes, each holding a value and two pointers.
• Index access: ArrayList jumps straight there. LinkedList walks node by node from the nearest end.
• Insert or delete at the front: LinkedList just relinks pointers. ArrayList shifts every later element.
• In practice ArrayList usually wins anyway — contiguous memory is cache-friendly, and node hopping is not.
• Each LinkedList node carries pointer overhead, so it uses far more memory per element.
• Need front-and-back operations? Use ArrayDeque, not LinkedList. It is faster and leaner.

Example

import java.util.*;

public class Main {
    static final int N = 20_000;

    public static void main(String[] args) {
        System.out.println("insert at index 0, " + N + " times");
        System.out.println("  ArrayList  : " + timeInsertFront(new ArrayList<>()) + " ms");
        System.out.println("  LinkedList : " + timeInsertFront(new LinkedList<>()) + " ms");

        System.out.println("random get(i), " + N + " times");
        System.out.println("  ArrayList  : " + timeRandomGet(fill(new ArrayList<>())) + " ms");
        System.out.println("  LinkedList : " + timeRandomGet(fill(new LinkedList<>())) + " ms");
    }

    static long timeInsertFront(List<Integer> list) {
        long t = System.nanoTime();
        for (int i = 0; i < N; i++) list.add(0, i);
        return (System.nanoTime() - t) / 1_000_000;
    }

    static List<Integer> fill(List<Integer> list) {
        for (int i = 0; i < N; i++) list.add(i);
        return list;
    }

    static long timeRandomGet(List<Integer> list) {
        Random rnd = new Random(42);
        long sum = 0;
        long t = System.nanoTime();
        for (int i = 0; i < N; i++) sum += list.get(rnd.nextInt(N));
        long ms = (System.nanoTime() - t) / 1_000_000;
        if (sum == Long.MIN_VALUE) System.out.println("unreachable");
        return ms;
    }
}

LinkedList wins on paper at the front, loses in reality almost everywhere else.