Почему на практике ArrayList часто быстрее LinkedList, несмотря на асимптотику?

Question

ArrayList хранит данные в непрерывной области памяти.Это хорошо работает с кэшами процессора.LinkedList использует разрозненные объекты и ссылки.Из-за этого возникает много кэш-промахов.В реальных приложениях ArrayList часто оказывается быстрее.

YeaHub · Accepted Answer

Хотя асимптотика иногда выглядит в пользу LinkedList, реальная производительность определяется не только ей.Локальность данныхArrayList:Элементы лежат подряд в памяти.Процессор эффективно загружает их в кэш.Последовательный обход очень быстрый.LinkedList:Каждый элемент — отдельный объект.Узлы разбросаны по куче.Каждый переход — переход по ссылке.Стоимость ссылокУ LinkedList:Больше объектов.Больше памяти.Больше работы для GC.Каждый Node содержит:значениессылку на следующийссылку на предыдущийПрактические последствияНа практике:ArrayList выигрывает в большинстве сценариев.LinkedList оправдан только при частых вставках/удалениях по известному узлу.Даже add/remove в середине часто быстрее у ArrayList.Краткий выводArrayList чаще быстрее LinkedList из-за лучшей локальности памяти, меньшего количества объектов и эффективной работы кэша.