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

info@vsetut.pro

Стать автором

Вернуться

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

23.02.2026 10:20:52 | Хабр

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подробнее

Читайте также

Как я сделал автоматический перевод постов у себя в блоге с помощью ChatGPT
23.02.2026 10:09:18 | Хабр

Взлет и крах первого портативного компьютера: Osborne 1
23.02.2026 10:05:40 | Хабр

Я дал 100 AI-агентам равный бюджет — они изобрели кредиты под 15%
23.02.2026 09:54:59 | Хабр

AutoCraft 1.1.8: веб-панель для управления ПК и сервисами без привязки к Telegram
23.02.2026 09:53:54 | Хабр

Избавляемся от утечек памяти в Angular с withExperimentalAutoCleanupInjectors
23.02.2026 09:29:52 | Хабр

Что пугает лично меня в развитии искусственных помощников
23.02.2026 09:28:02 | Хабр

Первые мысли питониста о Си на примере игры «камень-ножницы-бумага»
23.02.2026 09:19:00 | Хабр

Как запустить новый XBox 360 рекомпилятор RexGlue
23.02.2026 09:18:13 | Хабр

Голоса в компьютере: игры начинают петь
23.02.2026 09:01:30 | Хабр

Вайбкодинг убил индустрию, или поминки по синьор-разработчикам
23.02.2026 08:46:07 | Хабр

[Predictive Loading] Дебаггинг тревоги инженера
23.02.2026 08:30:25 | Хабр

Недельный геймдев: #266 — 22 февраля, 2026
23.02.2026 08:27:12 | Хабр

Память на вес золота: к чему приведет дефицит NAND в 2026 году
23.02.2026 08:00:20 | Хабр

Организация репозитория программных пакетов с ограниченным доступом в Linux
23.02.2026 08:00:19 | Хабр

Как войти в Open Source? С нуля до первого контрибьюта
23.02.2026 07:20:12 | Хабр

Зачем джуну Open Source? И как начать?
23.02.2026 07:20:12 | Хабр

Взлом LLM-агентов на уровне архитектуры: почему они беззащитны перед структурными инъекциями
23.02.2026 07:06:40 | Хабр

Ты где? Обзор самых популярных технологий позиционирования RFID, BLE и UWB. Часть 1
23.02.2026 07:05:10 | Хабр

Цифровая эволюция России: анализ главных трендов Рунета за 10 лет
23.02.2026 07:00:08 | Хабр

[Перевод] Пузырь ИИ — это не то, что вы думаете
23.02.2026 06:54:41 | Хабр

Три аккаунта ChatGPT и один прокси: как перестать следить за лимитами
23.02.2026 06:53:05 | Хабр

Архитектурная бомба замедленного действия
23.02.2026 06:48:21 | Хабр

Как продают иллюзию входа в QA в 2026 году
23.02.2026 06:26:15 | Хабр

Квантовый блокчейн: какие компании и страны его разрабатывают
23.02.2026 06:13:59 | Хабр

Давайте объединим линейную и геометрическую алгебры. На простом примере. Часть 1
23.02.2026 06:00:57 | Хабр

Бойцовский клуб: стиль повествования, фишка 25-го кадра, альтер-эго и кто такая Марла?
23.02.2026 05:59:18 | Хабр

Авторизация 2026: Почему вам больше не нужна форма регистрации (и как внедрить Яндекс ID, VK и Google)
23.02.2026 05:59:15 | Хабр

Величайший системный кризис человечества: в шаге от катастрофы XXI века
23.02.2026 05:46:55 | Хабр

Организация импортов в React + TypeScript: настройка ESLint для порядка и чистоты кода
23.02.2026 05:02:59 | Хабр

Трампу запретили тарифицировать, а также возврат доллара на Мосбиржу
23.02.2026 04:59:24 | Хабр

На фото — враг Android-смартфонов первой половины 2010-х
23.02.2026 04:12:05 | Хабр

[Перевод] ИИ против капитализма: пришло время 15-часовой рабочей недели
22.02.2026 20:59:33 | Хабр

Что такое дерево метрик и зачем оно нужно?
22.02.2026 20:56:14 | Хабр

Грейды в аналитике: как не остаться вечным джуном?
22.02.2026 20:51:22 | Хабр

Как я сделал Chrome Dino в Telegram Mini App
22.02.2026 20:24:12 | Хабр

Смотреть все

НОВОСТИ

Вербное воскресенье в 2026 году: смысл и традиции православного праздника
13.04.2026 00:10:00 | Lenta.ru

"Финуслуги": в I квартале чаще всего страховали марки Lada, Toyota и Hyundai
07.04.2026 01:25:11 | ТАСС

Иранцы потроллили США в ответ на ультиматум: «8 вечера — неудобное время, перенесите»
07.04.2026 01:23:27 | Life.ru

Иранцы потроллили США в ответ на угрозу «обрушить ад»: 8 вечера — неудобное время, перенесите
07.04.2026 01:23:27 | Life.ru

На Камчатке впервые откроется факультет журналистики
07.04.2026 01:21:14 | ТАСС

53-летняя Кармен Электра снялась топлес в честь Пасхи и порадовала фанатов
07.04.2026 01:16:26 | Lenta.ru

На Камчатке у сбившего насмерть подростка были неисправны тормоза в автомобиле
07.04.2026 01:16:23 | ТАСС

День рождения Михаила Круга 2026: биография, интересные факты и лучшие песни легенды шансона
07.04.2026 01:15:00 | Life.ru

«Слоеный пирог» в городе: Российские силы закрепились в промзоне и частном секторе Константиновки
07.04.2026 01:13:54 | Life.ru

Раскрыт план Евросоюза против Венгрии
07.04.2026 01:13:38 | Lenta.ru

В ВСУ приготовились к потере Донбасса
07.04.2026 01:08:12 | Lenta.ru

Взрывы в небе над Парижем помешали сесть пассажирскому самолету
07.04.2026 01:05:49 | Lenta.ru

В МИД предупредили о катастрофе в Иране «страшнее чернобыльской»
07.04.2026 01:05:41 | Lenta.ru

Минэнерго Подмосковья предупредило о новой схеме кражи аккаунтов на «Госуслугах»
07.04.2026 01:05:36 | Life.ru

Мошенники начали воровать аккаунты россиян на «Госуслугах», обещая скидки на ЖКУ
07.04.2026 01:05:36 | Life.ru

Журналист Патернотте: Нидерланды впустили в ЕС офицера ВСУ из "черного списка"
07.04.2026 01:03:58 | ТАСС

Иран полагает, что риск блокировки Баб-эль-Мандеба подталкивает США к диалогу
07.04.2026 01:00:19 | ТАСС

Названы семь шагов для восстановления глубокого сна
07.04.2026 01:00:03 | Lenta.ru

Мобилизация на Украине оказалась под угрозой срыва
07.04.2026 01:00:00 | Lenta.ru

Гала-концерт к 125-летию Большого зала Московской консерватории пройдет 7 апреля
07.04.2026 00:50:51 | ТАСС

Аэропорт Ярославля ограничил полеты
07.04.2026 00:48:27 | РБК

L'AntiDiplomatico: Украина, атаковав объекты КТК, перешла опасную черту
07.04.2026 00:47:00 | Российская Газета

Фицо: Украина может угрожать ЕС военным опытом после вступления
07.04.2026 00:45:52 | Life.ru

Агент Его Величества? Как Дуров связан с Лондоном и почему бесится из-за блокировки Telegram
07.04.2026 00:45:00 | Life.ru

Число погибших при пожаре на «Нижнекамскнефтехиме» выросло до 12
07.04.2026 00:43:59 | Коммерсантъ

Артем Дедков стал кандидатом на пост главного архитектора Москвы
07.04.2026 00:41:06 | РБК

Корабль Orion проводит финальный манёвр вокруг Луны
07.04.2026 00:39:10 | Life.ru

В ОП призвали выплачивать пособие беременным вне зависимости от дохода
07.04.2026 00:37:27 | ТАСС

Число погибших при пожаре на заводе в Нижнекамске достигло 12
07.04.2026 00:33:23 | РБК

CTK: в Чехии цена дизельного топлива достигла максимума за четыре года
07.04.2026 00:33:17 | ТАСС

Al Hadath: в Исфахане нефтехранилище подверглось бомбардировке
07.04.2026 00:32:52 | ТАСС

Средняя пенсия неработающих пенсионеров в феврале составила 25,6 тыс. рублей
07.04.2026 00:31:38 | ТАСС

Глава НАСА оценил шансы на встречу с внеземной жизнью
07.04.2026 00:31:26 | Lenta.ru

Еще один аэропорт России приостановил полеты
07.04.2026 00:31:22 | Коммерсантъ

МИД РФ: Россия и Египет обсуждают инициативу зернового хаба
07.04.2026 00:29:59 | ТАСС

Все новости

ВСЕ НОВОСТИ

ПИШИТЕ

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

info@vsetut.pro