Чем ArrayList отличается от LinkedList и что брать по умолчанию?

ArrayList хранит элементы в массиве. get(i) — прямой доступ O(1). add(e) в конец — O(1) амортизированно: когда массив заполнен, он растёт в 1,5 раза с копированием, но копирования редки. Вставка и удаление в середине — O(n): сдвиг хвоста через System.arraycopy (быстрый блочный сдвиг памяти).

LinkedList — двусвязный список узлов {prev, item, next}. get(i) — O(n): обход от ближайшего конца. Вставка и удаление — O(1), если узел уже найден (через ListIterator) или это края списка. add(i, x) по индексу сначала ищет позицию — O(n).

Почему ArrayList почти всегда выигрывает:

• элементы массива лежат подряд — процессор подгружает их в кэш блоками, а узлы LinkedList разбросаны по куче — промах кэша на каждом шаге;
• каждый узел — отдельный объект с заголовком и двумя ссылками: в разы больше памяти и работы сборщику;
• сдвиг массива arraycopy очень быстрый даже на тысячах элементов.

Когда LinkedList: в новом коде — почти никогда. Для очередей и стеков есть ArrayDeque (кольцевой массив). Исключение — частые вставки и удаления в середине при обходе итератором огромного списка, и то стоит измерить.