Операция выполнена!
Закрыть
info@vsetut.pro
Стать автором
Вернуться

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

23.02.2026 10:20:52 | Хабр
Хабы: Программирование, Клиентская оптимизация, Процессоры, Программирование микроконтроллеров

«Связанные списки — это goto структур данных.», — авторство приписывают разным системным программистам.

История из учебника

Все студенты, изучающие computer science, узнают о связанных списках на первом курсе по структурам данных. Их описание звучит привлекательно:

Преимущества (согласно учебникам):

- Вставки и удаления за O(1) в известных позициях

- Динамический размер: увеличиваются и уменьшаются согласно необходимости

- Пространство не тратится впустую: можно распределять ровно столько, сколько нужно

- Гибкость: простота реализации стеков, очередей и других структур

Недостатки (согласно учебникам):

- Поиск за O(n): необходим обход, начиная с головы списка

- Лишняя память: указатели добавляют оверхед

- Невозможность произвольного доступа: нельзя выполнять переходы в произвольные позиции

Вывод из учебника: «Используйте связанные списки, когда требуются частые вставки/удаления и не нужен произвольный доступ».

Вроде бы звучит разумно?

Проверка реальностью

А вот, чего учебники нам не говорят: связанные списки — это почти всегда плохой выбор.

Не потому, что ошибочен анализ «О» большого, в нём всё правильно, а потому, что он неполон. Он забывает про оборудование.

Читать далее
Подробнее
Читайте также
НОВОСТИ

ВСЕ НОВОСТИ
ПИШИТЕ

Техническая поддержка проекта ВсеТут

info@vsetut.pro

Copyright © 2026 - vsetut.pro