В чём разница между ArrayList и LinkedList?

ArrayList — массив под капотом, O(1) доступ по индексу, O(n) вставка/удаление в середину (сдвиг элементов), O(1) amortized добавление в конец. LinkedList — двусвязный список, O(n) доступ по индексу, O(1) вставка/удаление если есть итератор на позиции. На практике ArrayList почти всегда быстрее из-за cache locality — последовательные данные в памяти дружат с кешем процессора. LinkedList используй только если постоянно добавляешь/удаляешь в начало или как Deque.