# [Перевод] Структуры данных на практике. Глава 5: Связанные списки — убийцы кэша
BotHabr (tgi,2) → All – 10:35:02 2026-02-23
Опубликовано: Mon, 23 Feb 2026 10:20:52 GMT
Канал: Все статьи подряд / Программирование микроконтроллеров / Хабр
«Связанные списки — это goto структур данных.», — авторство приписывают разным системным программистам.История из учебникаВсе студенты, изучающие computer science, узнают о связанных списках на первом курсе по структурам данных. Их описание звучит привлекательно:Преимущества (согласно учебникам):- Вставки и удаления за O(1) в известных позициях- Динамический размер: увеличиваются и уменьшаются согласно необходимости- Пространство не тратится впустую: можно распределять ровно столько, сколько нужно- Гибкость: простота реализации стеков, очередей и других структурНедостатки (согласно учебникам):- Поиск за O(n): необходим обход, начиная с головы списка- Лишняя память: указатели добавляют оверхед- Невозможность произвольного доступа: нельзя выполнять переходы в произвольные позицииВывод из учебника: «Используйте связанные списки, когда требуются частые вставки/удаления и не нужен произвольный доступ».Вроде бы звучит разумно?Проверка реальностьюА вот, чего учебники нам не говорят: связанные списки — это почти всегда плохой выбор.Не потому, что ошибочен анализ «О» большого, в нём всё правильно, а потому, что он неполон. Он забывает про оборудование. Читать далее]]>
https://habr.com/ru/articles/996210/
BotHabr (tgi,2) → All – 10:35:02 2026-02-23
Опубликовано: Mon, 23 Feb 2026 10:20:52 GMT
Канал: Все статьи подряд / Программирование микроконтроллеров / Хабр
«Связанные списки — это goto структур данных.», — авторство приписывают разным системным программистам.История из учебникаВсе студенты, изучающие computer science, узнают о связанных списках на первом курсе по структурам данных. Их описание звучит привлекательно:Преимущества (согласно учебникам):- Вставки и удаления за O(1) в известных позициях- Динамический размер: увеличиваются и уменьшаются согласно необходимости- Пространство не тратится впустую: можно распределять ровно столько, сколько нужно- Гибкость: простота реализации стеков, очередей и других структурНедостатки (согласно учебникам):- Поиск за O(n): необходим обход, начиная с головы списка- Лишняя память: указатели добавляют оверхед- Невозможность произвольного доступа: нельзя выполнять переходы в произвольные позицииВывод из учебника: «Используйте связанные списки, когда требуются частые вставки/удаления и не нужен произвольный доступ».Вроде бы звучит разумно?Проверка реальностьюА вот, чего учебники нам не говорят: связанные списки — это почти всегда плохой выбор.Не потому, что ошибочен анализ «О» большого, в нём всё правильно, а потому, что он неполон. Он забывает про оборудование. Читать далее]]>
https://habr.com/ru/articles/996210/