Структуры данных
Структура данных — способ организации данных для более эффективного использования.
От структуры зависит, что система будет делать быстро: мгновенный доступ по ключу, дешёвую вставку или поддержку уникальности.
Структуры делятся на
- линейные (массив, связный список, стек, очередь)
- нелинейные (деревья, графы).
Рассмотрим 10 базовых структур и когда их использовать
Заметка: как читать сложность операций
O(1)— время не зависит от объёма данных;O(n)— растёт линейно с числом элементов;O(log n)— растёт медленно, каждый шаг отбрасывает часть данных.
1. Массив (Array)
Набор элементов, лежащих в памяти подряд; у каждого — индекс, нумерация обычно с нуля.
- адрес элемента вычисляется арифметически, поэтому:
- чтение по индексу —
O(1) - поиск значения —
O(n)перебором - вставка и удаление в середине —
O(n)из-за сдвига хвоста
- чтение по индексу —
- виды: одномерный (строка значений), двумерный (таблица), многомерный
Динамический массив сам расширяется при заполнении: когда место кончается, он целиком копируется в новый массив вдвое большего размера — это дорого, но случается всё реже по мере роста.
В среднем одна вставка в конец обходится дёшево — амортизированное O(1).
Когда использовать:
- небольшие наборы значений, сортировка;
- основа сложных структур — стеки, очереди и списки чаще всего построены на массивах.
Пример: строки отчёта — двумерный массив; JSON-массив товаров в корзине.
Характерный тип БД: реляционные базы данных.
2. Связный список (Linked list)
Элементы — узлы, разбросанные по памяти произвольно; каждый узел хранит данные и указатель на следующий (в двусвязном — ещё и на предыдущий). Последовательность задают ссылки, а не положение элементов.
- доступа по индексу нет: до нужного элемента идут по цепочке от «головы» —
O(n) - вставка и удаление при известной позиции — переброска пары указателей,
O(1), без сдвига остальных элементов - плата за гибкость — дополнительная память на указатели в каждом узле
Когда использовать: частые вставки и у даления, заранее неизвестное число элементов; строительный материал для стеков и очередей, цепочек коллизий в хеш-таблицах (раздел 7) и списков смежности графа (раздел 10).
Пример: классическая файловая система (например, FAT) хранит файл как цепочку блоков диска: номер следующего блока записывается не в самом блоке, а в отдельной таблице (FAT).
Характерный тип БД: документо-ориентированные базы данных.
3. Стек (Stack)
Линейная структура с доступом только к вершине: последний пришёл — первым вышел (LIFO).
Операции: push (положить), pop (снять), peek (посмотреть вершину) — все за O(1).
Аналогия — стопка тарелок: чтобы взять нижнюю, снимают верхние.
Когда использовать:
- реализация рекурсии (стек вызовов),
- отмена действий и история изменений,
- проверка вложенности скобок,
- обход в глубину (раздел 10).
Пример: Ctrl+Z в редакторе — каждое действие пользователя кладётся на стек, отмена снимает верхнее и выполняет обратное.
Характерный тип БД: временные базы данных или кэши.
4. Очередь (Queue)
Линейная структура: первый пришёл — первым вышел (FIFO). Добавление в конец и извлечение из начала — O(1). Разновидности: двусторонняя очередь (deque) с доступом к обоим концам и очередь с приоритетом, где раньше обрабатывается более важный элемент.
Когда использовать:
- очередь на доступ к ограниченному ресурсу,
- буферы (например, ввода-вывода),
- сглаживание пиковых нагрузок,
- распределение задач между потоками.
Пример: очередь заявок в helpdesk — первый зарегистрированный первым уходит в обработку. Топики Apache Kafka устроены как распределённый журнал-очередь: запись — в конец, чтение — с начала (сообщения при чтении не удаляются — их можно перечитывать).
Характерный тип БД: Apache Kafka.
5. Множество (Set)
Хранит только уникальные элементы: дубликаты отбрасываются. Поддерживает те же операции, что в математике над множествами: объединение, пересечение, разность.
- порядок вставки не сохраняется (реализация на дереве отдаёт элементы в отсортированном порядке)
- на хеш-таблице проверка вхождения и добавление —
O(1)в среднем; на сбалансированном дереве —O(log n)
Когда использовать:
- дедупликация данных,
- сравнение и объединение наборов,
- данные, где важна уникальность, а не порядок.
Пример: уникальные ИНН из выгрузки; пересечение клиентских баз двух каналов продаж — общие покупатели. Вероятностный «родственник» множества, экономящий память, — фильтр Блума.
Характерный тип БД: NoSQL-базы данных.
6. Карта / словарь (Map)
Ассоциативный массив: пары «ключ — значение»; ключи уникальны, значения могут дублироваться.
Поиск по ключу — O(1) в среднем на хеш-таблице или O(log n) на дереве.
Множество и карта отвечают на вопрос «что хранится» (уникальные элементы; пары ключ — значение), а хеш-таблица и дерево — «как устроено внутри»: одну и ту же карту можно реализовать по-разному.
Когда использовать: словари соответствий и быстрые справочники — «код региона → название», «пользователь → его сессия».
Пример: «месяц → число дней»; в инфраструктуре картам соответствуют хранилища «ключ — значение».
Характерный тип БД: хранилища «ключ — значение».
7. Хеш-таблица (Hash table)
Самый распространённый способ реализовать карту. Хеш-функция — правило, превращающее ключ (строку, число) в индекс массива; для одного и того же ключа индекс всегда одинаковый.
При запросе ключ снова хешируется — и ячейка находится сразу: вставка, поиск и удаление — O(1) в среднем.
Коллизии — разные ключи получают один индекс — неизбежны: возможных ключей больше, чем ячеек.
Классические решения: цепочки (в ячейке живёт связный список всех попавших туда пар) и открытая адресация (пару кладут в ближайшую свободную ячейку по правилу перебора). В худшем случае — все ключи в одной ячейке — операции деградируют до O(n).
Когда использовать:
- кэши,
- сессии пользователей,
- счётчики,
- справочники вида «ИНН → клиент».
Пример: Redis — хранилище «ключ — значение» в памяти, внутри классическая хеш-таблица; при заполнении она расширяется постепенным rehash — пары переносятся в новую, большую таблицу с пересчётом позиций, без остановки сервиса.
Характерный тип БД: хранилища «ключ — значение».
8. Двоичное дерево поиска (Binary search tree)
Иерархия узлов, у каждого — ключ и не более двух потомков. Правило: всё, что меньше узла, лежит в левом поддереве, всё, что больше, — в правом.
- поиск: от корня (верхнего узла), меньше — влево, больше — вправо; на каждом шаге отбрасывается примерно половина ключей —
O(log n)в среднем - худший случай: при вставке элементов по возрастанию дерево вытягивается в линию, и поиск снова
O(n); самобалансирующиеся деревья (АВЛ, красно-чёрные) перестраивают узлы при вставке, сохраняя дерево низким, —O(log n)гарантированно - симметричный обход (левое поддерево → узел → правое) даёт отсортированную последовательность
Когда использовать: поиск, вставка и удаление за O(log n), данные всегда отсортированы.
Пример: индексы реляционных СУБД по умолчанию строятся на B-tree — обобщении двоичного дерева с сотнями ключей в узле (есть и другие типы индексов — hash, GIN, BRIN). В двоичном дереве 1 млн записей — примерно 20 шагов спуска, в B-tree — 3–4 уровня; в этом и причина выбора B-tree для дисковых индексов.
Характерный тип БД: реляционные базы данных.
9. Префиксное дерево (Trie)
Дерево для строк: ключ не хранится в узле, а «читается» по рёбрам от корня; конец ключа помечается признаком.
Сложность операций — O(L), где L — длина ключа, и не зависит от количества хранящихся ключей.
Когда использовать:
- автозаполнение (T9, поиск),
- словари,
- данные с повторяющимся началом: IP-адреса и префиксы подсетей.
Пример: по мере набора слова подсказки сужаются — это спуск по префиксному дереву: по набранному префиксу оно выдаёт все продолжения.
Характерный тип БД: поисковые системы.
10. Граф (Graph)
Набор вершин, соединённых рёбрами. Рёбра бывают направленными (A → B) и ненаправленными (A — B), могут иметь вес. Дерево — частный случай графа: связный и без циклов.
- представления: матрица смежности (таблица N×N, где N — число вершин; ячейка на пересечении строки и столбца показывает связь вершин) и список смежности (для каждой вершины — список соседей, экономнее по памяти на разреженных графах)
- основные обходы: в ширину (BFS — по уровням удалённости от стартовой вершины, через очередь) и в глубину (DFS — через стек или рекурсию)
Когда использовать: данные со сложными взаимными связями, анализ связей (кто с кем взаимодействует, что от чего зависит), построение маршрута из точки А в точку Б.
Пример:
- интеграционная карта «система → система» — граф
- социальные связи
- граф зависимостей задач в бэклоге
Характерный тип БД: графовые базы данных.
Массив vs связный список
| Критерий | Массив | Связный список |
|---|---|---|
| Память | непрерывный блок | узлы вразброс плюс указатели в каждом |
| Доступ по индексу | O(1) | O(n) — только обход от головы |
| Вставка/удаление в середине | O(n) — сдвиг хвоста | O(1) при известной позиции (поиск — O(n)) |
| Когда выбирать | известный размер, доступ по индексу | частые вставки/удаления, неизвестное число элементов |
Где применяются
| Структура | Где живёт |
|---|---|
| Массив | таблицы, JSON-массивы, основа сложных структур |
| Очередь | очереди задач, топики Kafka, буферы |
| Множество | дедупликация, теги, фильтры |
| Карта (на хеш-таблице) | хранилища «ключ — значение» (Redis), кэши, сессии |
| Дерево поиска (B-tree) | индексы реляционных СУБД |
| Префиксное дерево | автозаполнение, поиск, маршрутизация по префиксу |
| Граф | графовые СУБД, социальные связи, карты и маршруты |
Зачем знать аналитику?
- Собеседования: спрашивают на технических интервью наряду с БД и интеграциями
- Общий язык с разработчиками: понимать, почему индекс ускоряет отчёт, а кэш — это хеш-таблица
- Проектирование: различать модели данных с уникальными ключами (карта, множество), журналы-очереди, иерархии (деревья) и сети связей (графы)
- Оценка производительности: O-нотация в ответах разработчиков перестаёт быть шумом
Подборка материалов
- Основные структуры данных. Матчасть. Азы
- 10 структур данных, которые должен знать каждый разработчик
- Самые популярные структуры данных
- Стеки и очереди: как работают LIFO и FIFO
- Двоичное дерево поиска (BST) для начинающих
- Префиксное дерево (trie) — вставка и поиск
- Префиксное дерево — Algorithmica
- Коллизии хэш-функций и парадокс дней рождения
- Под капотом Redis: хеш-таблица
- Структуры данных для хранения графов
- Двоичное дерево, двоичное дерево поиска, двоичная куча, B-дерево
- B-Tree индекс и его производные в PostgreSQL
- Динамический (расширяющийся) массив — Algorithmica
- Множество — Основы алгоритмов
- Сложность операций для структур данных (шпаргалка)
- Собеседование на системного аналитика: вопросы и задачи в 2026 году
- Основы ООП
Видео
- Бинарное дерево поиска | Структуры данных и алгоритмы
- Динамический массив | Структуры данных и алгоритмы
- Префиксное (нагруженное, Trie) дерево — Структуры данных
- Очереди типов FIFO и LIFO | Структуры данных
- Множества (set). Операции над множествами
- Как устроена база данных? Кластеры, индексы, схемы
- B-tree индексы в базах данных на примере IndexedDB
Конференции
- Analystdays: Реверс-инжиниринг схемы данных: кейсы и подходы