Короткий ответ Различие — во внутренней структуре. ArrayList построен на динамическом массиве Object[]: доступ по индексу — O(1), вставка или удаление в середине — O(n) из-за сдвига, добавление в конец — амортизированно O(1). LinkedList — двусвязный список: каждый элемент обёрнут в узел со ссылками на соседей; вставка в найденную позицию сводится к перестановке ссылок, но поиск позиции идёт перебором за O(n). Как это работает подробнее ArrayList хранит элементы в массиве, который автоматически расширяется при заполнении; элементы лежат подряд, поэтому итерация быстрая и хорошо используется кэш процессора. LinkedList на каждый элемент создаёт отдельный объект-узел со ссылками на предыдущий и следующий; узлы разбросаны по памяти, поэтому структура проигрывает и ArrayList, и более современным коллекциям. Доступ по индексу: у ArrayList O(1), у LinkedList — перебор от начала или конца, O(n). Вставка в середину: у ArrayList сдвиг последующих элементов — O(n); у LinkedList после поиска узла — O(1), но сам поиск стои
Загрузка…
