Коллекции trainee
Почему ArrayList на практике быстрее LinkedList?
Ответ
Cache locality. ArrayList хранит элементы в непрерывном куске памяти — процессор подгружает целые блоки в L1/L2 кэш. У LinkedList узлы разбросаны по куче — каждый next() это cache miss, что и замедляет обход на практике.
Разбор: Ключ — cache locality: непрерывный массив ArrayList хорошо ложится в кэши процессора, тогда как разбросанные по куче узлы LinkedList дают cache miss на каждом next(). Дистракторы подменяют это другими причинами: ни final-методы и инлайнинг, ни автобоксинг (ArrayList тоже хранит объекты-Integer, а не примитивы) не объясняют разницу, а доступ по индексу в ArrayList — это O(1), а не бинарный поиск.
Хочешь так же по своей компании — с вопросами по грейдам и задачами? Закажи гайд или забери свежее в Telegram.