Структуры данных, которые должен знать каждый разработчик
Основы4 минРедакция Innovialabs
Коротко
Структуру данных выбирают по главной операции: доступ по индексу — массив, поиск по ключу — хеш-таблица, порядок и диапазоны — дерево, «самый важный элемент» — куча, связи между объектами — граф.
Главное правило выбора
Структура данных — это способ разложить данные в памяти так, чтобы частая операция была дешёвой. Сначала определите, что ваш код делает чаще всего: читает по индексу, ищет по ключу, добавляет в конец, достаёт минимальный элемент или ходит по связям. От ответа зависит выбор.
Таблица стоимости операций
Оценки даны для типичной реализации в среднем случае.
| Структура | Доступ | Поиск | Вставка | Удаление |
|---|---|---|---|---|
| Массив (динамический) | O(1) | O(n) | O(1) в конец, O(n) в середину | O(n) |
| Связный список | O(n) | O(n) | O(1) при известном узле | O(1) при известном узле |
| Стек | O(1) к вершине | — | O(1) | O(1) |
| Очередь | O(1) к началу | — | O(1) | O(1) |
| Хеш-таблица | — | O(1) | O(1) | O(1) |
| Сбалансированное дерево поиска | — | O(log n) | O(log n) | O(log n) |
| Куча (heap) | O(1) к минимуму | O(n) | O(log n) | O(log n) для минимума |
Массив
Элементы лежат в памяти подряд, поэтому доступ по индексу мгновенный, а перебор быстрый благодаря кешу процессора. Вставка в середину требует сдвига всех следующих элементов. Используйте по умолчанию — для большинства списков это лучший выбор.
Связный список
Каждый узел хранит значение и ссылку на следующий. Вставка и удаление дешёвые, если у вас уже есть ссылка на узел, но доступ по индексу требует прохода с начала. На практике нужен редко: например, внутри LRU-кеша или очередей с частым удалением из середины.
Стек и очередь
- Стек (LIFO) — последний вошёл, первый вышел. История «Отменить», разбор скобок, обход в глубину, стек вызовов функций.
- Очередь (FIFO) — первый вошёл, первый вышел. Обработка задач по порядку, обход в ширину, буферы сообщений.
В Python для очереди используйте collections.deque, в JavaScript — массив с push/pop для стека, а для очереди при больших объёмах лучше отдельная реализация, так как shift сдвигает элементы.
Хеш-таблица и множество
Хеш-таблица хранит пары «ключ — значение» и находит значение по ключу в среднем за константное время. Это dict в Python, Map и объекты в JavaScript, HashMap в Java. Множество — та же хеш-таблица без значений: быстрая проверка «есть ли элемент» и удаление дубликатов.
Типичный приём: заменить вложенный цикл поиска на заранее построенный словарь — и квадратичный алгоритм становится линейным.
Деревья
Дерево — иерархия узлов с одним корнем. Двоичное дерево поиска хранит элементы упорядоченно: слева меньше, справа больше. В сбалансированном виде поиск, вставка и удаление идут за O(log n), а ещё можно получать элементы по порядку и искать диапазоны. На деревьях построены индексы баз данных (B-деревья), DOM, файловые системы.
Куча
Куча быстро отдаёт минимальный (или максимальный) элемент и быстро принимает новые. Это основа очереди с приоритетом: планировщики задач, алгоритм Дейкстры, выбор top-K элементов. В Python — модуль heapq, в Java — PriorityQueue.
Граф
Граф описывает объекты и связи между ними: дороги, друзья в соцсети, зависимости пакетов. Обычно хранится как список смежности — словарь «вершина — список соседей». Основные алгоритмы: обход в ширину и в глубину, кратчайшие пути, топологическая сортировка.
Как выбрать: шпаргалка
- Нужен упорядоченный список и доступ по номеру — массив.
- Нужно быстро найти по ключу или убрать дубли — хеш-таблица / множество.
- Нужно обрабатывать в порядке поступления — очередь; в обратном — стек.
- Нужен всегда самый срочный элемент — куча.
- Нужен порядок, диапазоны, «следующий больший» — дерево поиска.
- Данные — это связи — граф.
Частые ошибки
- Искать в массиве в цикле, когда можно один раз построить словарь.
- Использовать связный список «потому что вставка O(1)», хотя элемент сначала нужно найти за O(n).
- Забыть, что хеш-таблица не гарантирует сортировку по ключам.
- Оптимизировать структуру до того, как замерили, где реальное узкое место.