Структуры данных
| Определение | способ хранения и организации данных для эффективного доступа и изменения |
|---|---|
| Линейные | массив, связный список, стек, очередь, дек |
| Ассоциативные | хеш-таблица, множество, словарь |
| Иерархические | деревья, кучи, префиксные деревья |
| Сетевые | графы |
| Ключевая книга | Никлаус Вирт «Алгоритмы + структуры данных = программы» (1976) |
Структура данных — способ организации и хранения данных в памяти компьютера, определяющий, какие операции с ними выполняются быстро, а какие медленно. Один и тот же набор чисел можно хранить в массиве, связном списке, хеш-таблице или дереве, и от этого выбора зависит, займёт поиск элемента наносекунды или секунды. Никлаус Вирт выразил эту связь названием книги «Алгоритмы + структуры данных = программы» (1976).
Различают абстрактный тип данных — что структура умеет (например, «очередь: добавить в конец, взять из начала») — и его реализацию — как это устроено в памяти (кольцевой буфер или связный список). Скорость операций описывают с помощью O-нотации.
Основные структуры
| Структура | Доступ по индексу | Поиск | Вставка / удаление | Особенности |
|---|---|---|---|---|
| Массив (динамический) | O(1) | O(n) | O(n), в конец — O(1) амортизированно | непрерывная память, дружит с кэшем процессора |
| Связный список | O(n) | O(n) | O(1) при известной позиции | нет перераспределения памяти, но медленный обход |
| Стек | — | — | O(1) на вершине | последним вошёл — первым вышел (LIFO) |
| Очередь, дек | — | — | O(1) с концов | первым вошёл — первым вышел (FIFO) |
| Хеш-таблица | — | O(1) в среднем | O(1) в среднем | нет порядка, нужна хорошая хеш-функция |
| Сбалансированное дерево поиска | — | O(log n) | O(log n) | хранит ключи упорядоченно, диапазонные запросы |
| Куча (двоичная) | — | минимум за O(1) | O(log n) | очередь с приоритетом |
| Граф | — | зависит от алгоритма | — | связи «многие ко многим» |
Массив
Элементы лежат в памяти подряд, поэтому адрес любого вычисляется по индексу мгновенно, а последовательный проход очень быстр благодаря кэшу процессора. Динамический массив (list в Python, Vec в Rust, срез в Go) при переполнении выделяет память с запасом и копирует элементы, поэтому добавление в конец в среднем стоит O(1). Вставка в середину требует сдвига всех последующих элементов.
Связный список
Каждый элемент хранит значение и ссылку на следующий (в двусвязном — и на предыдущий). Вставка и удаление в известном месте дешевы, но доступ к i-му элементу требует прохода от начала, а разбросанные по памяти узлы плохо используют кэш. На практике связные списки нужны реже, чем кажется по учебникам; их основа — в реализации очередей, LRU-кэшей и аллокаторов.
Стек и очередь
Стек — как стопка тарелок: кладём и берём сверху. Он используется для вызовов функций (стек вызовов), отмены действий, разбора скобок и обхода в глубину. Очередь — как очередь в магазине: обработка задач в порядке поступления, обход графа в ширину, буферы сообщений. Дек (deque) позволяет добавлять и забирать с обоих концов.
Хеш-таблица
Хеш-функция превращает ключ в номер ячейки, и поиск, вставка и удаление в среднем выполняются за O(1). На хеш-таблицах построены словари и множества почти во всех языках, кэши, индексы и дедупликация. Подробнее — в статье Хеш-таблица.
Деревья и кучи
Деревья поиска (красно-чёрные, AVL, B-деревья) хранят ключи упорядоченно и находят, вставляют и удаляют за O(log n), поддерживая запросы по диапазону; B-деревья лежат в основе индексов баз данных. Куча — дерево, где родитель не больше потомков; она быстро выдаёт минимальный элемент и используется в очередях с приоритетом, планировщиках и алгоритме Дейкстры. Префиксное дерево (trie) хранит строки по символам — для автодополнения и маршрутизации. Подробнее — в статье Дерево и граф.
Графы
Граф — множество вершин и рёбер между ними: дороги между городами, зависимости пакетов, связи в соцсети, ссылки между страницами. Хранится списками смежности (экономно для редких связей) или матрицей смежности (быстрая проверка ребра).
Структуры в Python
from collections import deque, Counter, defaultdict
import heapq
stack = []; stack.append(1); stack.pop() # список как стек
queue = deque(); queue.append("a"); queue.popleft() # очередь O(1) с обоих концов
index = {"alice": 1, "bob": 2} # dict — хеш-таблица
unique = set(["a", "b", "a"]) # множество
counts = Counter("mississippi") # подсчёт элементов
graph = defaultdict(list); graph["a"].append("b") # список смежности
tasks = []
heapq.heappush(tasks, (2, "написать тесты"))
heapq.heappush(tasks, (1, "починить прод"))
print(heapq.heappop(tasks)) # (1, 'починить прод') — минимальный приоритет
Модули collections и heapq стандартной библиотеки покрывают большинство повседневных задач;[3][4] сложность операций со встроенными типами сведена в таблицу на Python Wiki.[5] В других языках есть аналоги — например, модуль std::collections в Rust.[6]
Как выбирать
- Определите самые частые операции: поиск по ключу, доступ по порядку, добавление в конец, извлечение минимума, диапазонные запросы.
- Подберите структуру, где именно они дешевы: частая проверка «есть ли элемент» — множество, а не список; извлечение самого срочного — куча; упорядоченный обход — дерево или отсортированный массив.
- Учитывайте память и кэш: для небольших объёмов простой массив часто быстрее «правильной» структуры.
- Используйте готовые реализации стандартной библиотеки — они отлажены и оптимизированы.
Систематическое изложение с доказательствами — в учебнике Кормена и соавторов.[1] Подробно о встроенных структурах Python — в официальном руководстве.[2]