Чем отличается ArrayList от LinkedList

ArrayList — это динамический массив, а LinkedList — двусвязный список. Каждая структура оптимизирована для разных сценариев.

ArrayList:

• Доступ по индексу за O(1) — прямое обращение к элементу массива.
• Поиск по значению за O(N) — линейный перебор.
• Вставка/удаление в конец в среднем за O(1), но при исчерпании емкости — O(N) на копирование.
• Вставка/удаление в середину за O(N) — сдвиг элементов через System.arraycopy().
• Минимальные накладные расходы на хранение (только ссылки в массиве).

LinkedList:

• Доступ по индексу за O(N) — последовательный обход от начала или конца.
• Доступ к первому и последнему элементу за O(1).
• Вставка/удаление в начало и конец за O(1).
• Вставка/удаление в произвольную позицию за O(1), но поиск позиции за O(N).
• Большие накладные расходы: каждый элемент — объект Node с двумя ссылками.

На практике ArrayList предпочтителен в абсолютном большинстве случаев. Он выигрывает за счет локальности данных в кэше процессора: элементы массива лежат рядом в памяти, что позволяет CPU эффективно предзагружать данные. Элементы LinkedList разбросаны по heap, что приводит к cache miss при обходе.

На собеседовании: начните с таблицы сложностей. Объясните, почему ArrayList быстрее на практике даже там, где LinkedList выигрывает теоретически (cache locality). LinkedList оправдан только при частых вставках/удалениях в начало.