Структуры данных на практике. Глава 5: Связанные списки — убийцы кэша

«Связанные списки — это goto структур данных.», — авторство приписывают разным системным программистам.
История из учебника
Все студенты, изучающие computer science, узнают о связанных списках на первом курсе по структурам данных. Их описание звучит привлекательно:
Преимущества (согласно учебникам):
- Вставки и удаления за O(1) в известных позициях
- Динамический размер: увеличиваются и уменьшаются согласно необходимости
- Пространство не тратится впустую: можно распределять ровно столько, сколько нужно
- Гибкость: простота реализации стеков, очередей и других структур
Недостатки (согласно учебникам):
- Поиск за O(n): необходим обход, начиная с головы списка
- Лишняя память: указатели добавляют оверхед
- Невозможность произвольного доступа: нельзя выполнять переходы в произвольные позиции
Вывод из учебника: «Используйте связанные списки, когда требуются частые вставки/удаления и не нужен произвольный доступ».
Вроде бы звучит разумно?
Проверка реальностью
А вот, чего учебники нам не говорят: связанные списки — это почти всегда плохой выбор.
Не потому, что ошибочен анализ «О» большого, в нём всё правильно, а потому, что он неполон. Он забывает про оборудование.



















