Структуры данных
Способы организовать данные в памяти так, чтобы нужные операции — поиск, вставка, удаление — выполнялись быстро.
Структура данных — способ разместить данные в памяти и связать их между собой. Одни и те же записи можно хранить по-разному, и от выбора зависит скорость работы: в одной структуре поиск занимает микросекунды, в другой — секунды на тех же данных. Выбор структуры — одно из главных решений при проектировании программы, наравне с выбором алгоритма.
Основные структуры
- Массив — элементы подряд в памяти. Доступ по номеру мгновенный, но вставка в середину требует сдвинуть все последующие элементы.
- Связный список — каждый элемент хранит ссылку на следующий. Вставлять и удалять легко, но чтобы найти элемент, нужно пройти список с начала.
- Стек — «последним пришел, первым ушел», как стопка тарелок. На стеке держится вызов функций, в том числе рекурсия.
- Очередь — «первым пришел, первым ушел». Так устроены очереди задач и сообщений, например в RabbitMQ.
- Хеш-таблица — хранит пары «ключ — значение» и находит значение по ключу почти мгновенно. На ней основаны словари в языках программирования и хранилища вроде Redis.
- Дерево — иерархия узлов. Сбалансированные деревья поиска держат данные упорядоченными, а B-деревья лежат в основе индексов баз данных.
- Граф — узлы и связи между ними: дороги между городами, друзья в соцсети, зависимости между задачами.
Как сравнивают скорость
Скорость операций описывают O-нотацией: как растет время работы с ростом объема данных. O(1) — время не зависит от объема, O(log n) — растет очень медленно, O(n) — пропорционально числу элементов.
| Структура | Найти по ключу или значению | Добавить элемент |
|---|---|---|
| Массив (неупорядоченный) | O(n) | O(1) в конец |
| Связный список | O(n) | O(1), если место известно |
| Хеш-таблица | O(1) в среднем | O(1) в среднем |
| Сбалансированное дерево | O(log n) | O(log n) |
Для миллиона записей разница между O(n) и O(log n) — это миллион шагов против двадцати.
Как выбирают структуру
- Частый поиск по ключу — хеш-таблица.
- Нужен порядок и поиск по диапазону («все платежи за март») — дерево.
- Обработка задач по очереди — очередь; отмена действий — стек.
- Связи и маршруты — граф.
На практике готовые структуры есть в каждом языке и в базах данных, писать их с нуля почти не приходится. Но понимать, что лежит внутри, нужно: именно неудачный выбор структуры чаще всего превращает быструю на тестах программу в медленную на реальных объемах.