Почему ArrayList обычно обходит LinkedList даже там, где асимптотика формально в пользу связного списка?
- Почему LinkedList медленнее ArrayList на практике?
- Почему LinkedList на практике почти всегда проигрывает ArrayList, хотя вставка в середину у него формально O(1)?
Локальность данных: массив лежит подряд и попадает в кэш процессора блоками, узлы LinkedList разбросаны по куче — промах кэша на каждом шаге. Плюс узел — отдельный объект с заголовком и двумя ссылками.
- Промах кэша в ~100 раз дороже попадания
- Больше памяти и работы GC у LinkedList
- System.arraycopy сдвигает тысячи элементов очень быстро
А ещё Измеряют через JMH, а не по асимптотике
Подробно
Асимптотика игнорирует константу, а на современном железе именно она решает: промах кэша стоит на два порядка дороже попадания. Массив читается предсказуемо и подхватывается предвыборкой, тогда как переход по ссылке на случайный адрес кучи такой возможности не даёт. Добавьте накладные расходы: узел хранит заголовок объекта и две ссылки, то есть память на элемент кратно больше, а больший объём — это ещё и больше промахов. Практический вывод: по умолчанию берут ArrayList, а LinkedList рассматривают лишь при интенсивной работе с концами списка через итератор.
Что хотят услышать
- Кэш и локальность.
- Накладные расходы на узлы.
Частые ошибки
- Выбирать структуру только по таблице асимптотик.
- Считать какую-либо из этих коллекций потокобезопасной.
Проверьте себя
Несколько верных вариантов. Подумайте, потом откройте ответ.
Показать варианты и ответ
- ✗LinkedList синхронизирован, а ArrayList — нет, поэтому каждая операция связного списка платит за блокировку
- ✓Элементы массива лежат подряд, и обход дружит с кэшем процессора
- ✓Каждый узел LinkedList — отдельный объект с двумя ссылками
- ✓Узлы разбросаны по куче, и обход даёт промахи кэша
Что спросят дальше
- Во сколько примерно раз промах кэша дороже попадания?
- Как измерить разницу корректно, не наткнувшись на ошибки бенчмаркинга?
- Почему ArrayDeque быстрее LinkedList в роли очереди?
- В каком случае удаление через итератор действительно даёт выигрыш?
Разбор темы
- LinkedList и миф о дешёвой вставке
Двусвязные узлы, реальная стоимость операций, cache locality и почему ArrayList/ArrayDeque почти всегда лучше.
Связанные вопросы
Разбор собеседования с sotto
После собеседования sotto разбирает разговор: оценка, каждый вопрос — хорошо, частично или слабо, чего не хватило в ответе и над чем поработать к следующему разу. Первые 30 минут бесплатно.