🧱 Структуры данных
Массив, список, стек, очередь, хэш-таблица, дерево, куча, граф: операции и сложность.
Шпаргалки · Данные · #data-structures #algorithms #theory
Сложность операций
| Структура | Доступ | Поиск | Вставка | Удаление |
|---|---|---|---|---|
| Массив | O(1) | O(n) | O(n) | O(n) |
| Связный список | O(n) | O(n) | O(1)* | O(1)* |
| Стек, очередь | O(n) | O(n) | O(1) | O(1) |
| Хэш-таблица | n/a | O(1) средн. | O(1) средн. | O(1) средн. |
| Сбалансированное дерево | O(log n) | O(log n) | O(log n) | O(log n) |
| Куча (heap) | O(1) мин/макс | O(n) | O(log n) | O(log n) |
* при наличии ссылки на узел.
Что выбрать
| Задача | Структура |
|---|---|
| Доступ по индексу | массив |
| Частые вставки в начало и конец | дек, связный список |
| Отмена действий, обход в глубину | стек (LIFO) |
| Обработка по порядку, обход в ширину | очередь (FIFO) |
| Поиск по ключу | хэш-таблица (словарь) |
| Отсортированные данные, диапазоны | дерево (BST, B-tree) |
| Минимум или максимум | куча, приоритетная очередь |
| Уникальные значения | множество (set) |
| Связи между объектами | граф |
| Поиск по префиксу | префиксное дерево (trie) |
Основные структуры
- Массив. Элементы подряд в памяти, быстрый доступ по индексу.
- Связный список. Узлы со ссылкой на следующий (и предыдущий в двусвязном).
- Стек.
push,pop,peek: последний пришёл, первый ушёл. - Очередь.
enqueue,dequeue: первый пришёл, первый ушёл. - Хэш-таблица. Хэш ключа даёт позицию; коллизии решают цепочками или открытой адресацией.
- Двоичное дерево поиска. Левый потомок меньше узла, правый больше. Самобалансирующиеся: AVL, красно-чёрное.
- Куча. Полное дерево, где родитель не больше (min-heap) или не меньше (max-heap) потомков.
- Граф. Вершины и рёбра; хранится списком смежности (экономно) или матрицей (быстрая проверка ребра).
Обходы
| Обход | Структура | Применение |
|---|---|---|
| В глубину (DFS) | стек или рекурсия | связность, циклы, топологическая сортировка |
| В ширину (BFS) | очередь | кратчайший путь без весов |
| Дейкстра | приоритетная очередь | кратчайший путь с неотрицательными весами |
Реализации в языках
| Структура | Python | JavaScript | Java |
|---|---|---|---|
| Динамический массив | list |
Array |
ArrayList |
| Словарь | dict |
Map, Object |
HashMap |
| Множество | set |
Set |
HashSet |
| Очередь | collections.deque |
Array (shift) |
ArrayDeque |
| Куча | heapq |
нет встроенной | PriorityQueue |
Совет: На собеседовании сначала назовите сложность по времени и по памяти, потом оптимизируйте.