Коллекции middle
ArrayList vs LinkedList — где быстрее вставка в середину?
Ответ
У LinkedList O(1) на саму вставку, но O(n) на поиск позиции. В реальности ArrayList почти всегда быстрее из-за локальности в кэше CPU.
Разбор: У LinkedList сама вставка O(1), но чтобы дойти до середины, нужен обход за O(n); у ArrayList — O(n) на сдвиг, но за счёт локальности данных в кэше и быстрого копирования памяти он на практике почти всегда выигрывает. Главная ловушка — считать, что отсутствие сдвига автоматически делает LinkedList быстрее, игнорируя стоимость поиска позиции и промахи кэша.
Хочешь так же по своей компании — с вопросами по грейдам и задачами? Закажи гайд или забери свежее в Telegram.