ArrayList против LinkedList: спор, который ИИ всё ещё проигрывает практике

Вот важная новость с фронта ИИ: sproshchaev 14 минут назад ArrayList против LinkedList: спор, который ИИ всё ещё проигрывает практике Средний 14 мин 684 Блог компании OTUS Java * Программирование * Алгоритмы * Карьера в IT-индустрии Аналитика Всем привет, меня зовут Сергей Прощаев, и в этой статье расскажу, почему один из самых старых споров в Java — ArrayList или LinkedList — до сих пор решается неправильно. Причём теперь неправильно его решают не только джуны на собеседованиях, но и языковые модели, которым мы всё чаще доверяем выбор структуры данных. Я Tech Lead и руководитель направления Java | Kotlin разработки в FinTech & E‑commerce и преподаю на курсах разработки и архитектуры в ОТУС.

За годы найма и код‑ревью я видел этот выбор сотни раз. И вот что любопытно: ответ, который дают на автомате, почти всегда расходится с тем, что показывает железо. А с приходом ИИ‑ассистентов разрыв стал заметнее, а не меньше.

Технические детали

Интуиция против железа: почему «правильный» по учебнику выбор проигрывает на практикеОткуда вообще взялся этот спорЛюбой, кто готовился к собеседованию по Java, знает «правильный» ответ наизусть. ArrayList — динамический массив: доступ по индексу за O(1), вставка и удаление в середине за O(n) из‑за сдвига элементов. LinkedList — двусвязный список: доступ за O(n), зато вставка и удаление за O(1), ведь надо лишь перецепить пару ссылок.

Вывод напрашивается сам: много вставок и удалений — LinkedList, много чтений по индексу — ArrayList. Красиво, логично, ложится в таблицу из двух колонок. Проблема не в самой нотации, а в её учебной интерпретации, которая формировалась в эпоху, когда разрыв между скоростью процессора и памяти был куда меньше сегодняшнего.

Сейчас обращение к данным, которых нет в кэше, может стоить на два‑три порядка дороже арифметической инструкции. И эта перемена ломает всю красивую таблицу из двух колонок. Помню, как на ревью мне прислали сервис обработки котировок, где горячий путь был построен на LinkedList — «потому что там частые вставки».

Отраслевые последствия

На деле код в основном не вставлял, а постоянно обходил коллекцию на каждый тик. Когда мы прогнали бенчмарк, замена на ArrayList ускорила горячий путь в несколько раз — ровно за счёт обхода. Реакция автора была классическая: «Но ведь Big O говорит обратное».

Big O действительно говорит обратное. Просто Big O абстрагируется от стоимости отдельных операций и поэтому ничего не говорит о поведении кэшей. Почему ИИ повторяет ту же ошибкуКазалось бы, при чём здесь ИИ.

Этот прогресс даёт важные сигналы о будущем отрасли, и технологический мир внимательно наблюдает.