Классификация структур данных — это разбиение способов организации данных в памяти на группы по общим признакам: по расположению элементов (линейные или нелинейные), по составу (примитивные или составные) и по изменчивости размера (статические или динамические). Один и тот же тип попадает сразу в несколько групп: массив одновременно линейный, составной и статический.
Содержание
Ниже — три оси классификации с явным разграничением близких терминов, обзорная таблица семи базовых структур со сложностью операций и короткий алгоритм выбора структуры под задачу. Это обзорная статья: глубокий разбор отдельных структур — по ссылкам в конце.
Три независимые оси: не путать признаки
Структуру данных классифицируют не по одному признаку, а по нескольким осям сразу. Путаница возникает, когда «линейный» противопоставляют «динамическому» — это признаки из разных осей, они не исключают друг друга.
Мини-словарь осей:
- расположение элементов — линейная структура (элементы идут цепочкой, у каждого один сосед слева и один справа) против нелинейной (у элемента может быть несколько соседей);
- состав — примитивная структура (неделимая единица) против составной (собрана из других структур);
- изменчивость — статическая (размер фиксирован заранее) против динамической (размер меняется во время работы программы).
Массив — линейный, составной, статический. Связный список — линейный, составной, динамический. Дерево — нелинейное, составное, динамическое. Одна структура получает по метке с каждой оси.
Линейные и нелинейные
Линейная структура хранит элементы в виде последовательности: есть первый элемент, последний, и у каждого промежуточного ровно один предыдущий и один следующий. К линейным относят массив, строку, стек, очередь, связный список.
Нелинейная структура допускает у элемента несколько связей. В дереве у узла один родитель, но несколько потомков; в графе связи между вершинами произвольны. К нелинейным относят деревья и графы.
Признак линейности — про логические связи, а не про физическое расположение в памяти. Массив линеен и лежит в памяти подряд, а связный список тоже линеен, но его узлы разбросаны по памяти и соединены указателями. То есть линейность не означает «лежит сплошным куском».
Примитивные и составные
Примитивная структура (базовый, простой тип) — неделимая с точки зрения программы единица: целое число, символ, логическое значение, ссылка (указатель). Для нее заранее известны размер в памяти и набор допустимых операций.
Составная структура (сложная, интегрированная) собирается из других структур — примитивных или, в свою очередь, составных. Массив, запись (структура с именованными полями), список, дерево — составные.
Граница «примитивный» зависит от языка и платформы, это упрощение. В одном языке строка — примитив, в другом (например, в C) строка — составная структура из массива символов. Размер целого числа тоже платформо-зависим, поэтому «примитив» — это не абсолют, а роль типа в конкретном языке.
Статические, полустатические и динамические
Ось изменчивости — про то, меняется ли число элементов и связей во время работы программы.
- Статические — размер фиксирован и выделяется заранее (на этапе компиляции или при создании). Пример: массив фиксированной длины, запись. Плюс — быстрый доступ по адресу; минус — нельзя выйти за исходный размер.
- Полустатические — длина переменная, но в заранее заданных пределах, с простыми операциями изменения (добавить/убрать с одного конца). Пример: стек и очередь. Это промежуточная категория из классической русскоязычной литературы по структурам данных; в англоязычных источниках такой отдельной группы обычно нет — это разница терминологий, а не сути.
- Динамические — размер ограничен только доступной памятью, элементы создаются и удаляются в любой момент, связи между ними задаются указателями. Пример: связный список, дерево, граф.
За гибкость динамических структур платят: указатели занимают дополнительную память, а доступ к элементу требует прохода по цепочке, а не вычисления адреса.
Обзор семи базовых структур
Ниже — назначение каждой структуры и типичная сложность базовых операций в нотации «О большое». Сложность показывает, как растет число шагов при росте числа элементов n.
| Структура | Назначение | Доступ по индексу | Поиск значения | Вставка | Удаление |
|---|---|---|---|---|---|
| Массив (динамич.) | хранение по индексу, быстрый доступ | O(1) | O(n) | O(1) в конце*, O(n) внутри | O(n) |
| Связный список | частые вставки/удаления по краям | O(n) | O(n) | O(1) в известной точке | O(1) в известной точке |
| Стек (LIFO) | откат, вложенность, парсинг | — | — | O(1) push | O(1) pop |
| Очередь (FIFO) | буфер задач, обход в ширину | — | — | O(1) enqueue | O(1) dequeue |
| Хеш-таблица | поиск по ключу | — | O(1) в среднем, O(n) в худшем | O(1) в среднем | O(1) в среднем |
| Дерево поиска | упорядоченное хранение, диапазоны | — | O(log n) если сбалансировано | O(log n) | O(log n) |
| Граф | связи «многие ко многим» | — | зависит от обхода | O(1) добавить ребро (список смежности) | зависит от представления |
Оговорки к таблице (это упрощенные типичные значения, не гарантии):
- «O(1) в конце*» для массива — амортизированная оценка: чаще всего вставка мгновенна, но при переполнении массив копируется целиком.
- Хеш-таблица дает O(1) только в среднем; при массовых коллизиях операции вырождаются в O(n).
- Дерево поиска дает O(log n) только в сбалансированном виде; несбалансированное дерево вырождается в цепочку с O(n).
- Для графа сложность зависит от представления (матрица или список смежности) и от алгоритма обхода.
Минимальные примеры на Python
Массив в Python — это тип list: доступ по индексу за O(1), добавление в конец амортизированно за O(1).
arr = [10, 20, 30]
print(arr[1]) # 20
arr.append(40)
print(arr) # [10, 20, 30, 40]Стек (LIFO) удобно строить на list, очередь (FIFO) — на deque, где удаление слева идет за O(1):
from collections import deque
stack = []
stack.append("a")
stack.append("b")
print(stack.pop()) # b (последним пришел - первым ушел)
queue = deque()
queue.append("a")
queue.append("b")
print(queue.popleft()) # a (первым пришел - первым ушел)Хеш-таблица в Python — это dict: поиск по ключу в среднем за O(1):
prices = {"hleb": 45, "moloko": 80}
print(prices["moloko"]) # 80Узел связного списка — пример указательной структуры: каждый узел хранит значение и ссылку на следующий:
class Node:
def __init__(self, value):
self.value = value
self.next = None
head = Node("A")
head.next = Node("B")
print(head.value, head.next.value) # A BКак выбрать структуру под задачу
Выбор идет не от «какая структура красивее», а от того, какая операция у вас самая частая. Короткий разбор по задаче:
- Нужен быстрый доступ по номеру позиции — массив.
- Часто вставляете и удаляете по краям, а доступ по индексу не важен — связный список, стек или очередь.
- Нужен принцип «последним пришел — первым ушел» (откат действий, разбор скобок) — стек.
- Нужен принцип «первым пришел — первым ушел» (очередь задач, обход в ширину) — очередь.
- Ищете по ключу и порядок не важен — хеш-таблица.
- Нужен порядок и поиск по диапазону («все значения от 10 до 20») — дерево поиска.
- Моделируете связи «многие ко многим» (маршруты, соцсвязи) — граф.
Если сомневаетесь, начните с массива или хеш-таблицы: они закрывают большинство прикладных задач, а к спискам, деревьям и графам переходят, когда упирается конкретная операция.
Выводы
- Классификация идет по трем независимым осям: расположение (линейные/нелинейные), состав (примитивные/составные), изменчивость (статические/динамические); одна структура получает метку с каждой оси.
- Линейность — про логические связи, а не про сплошное расположение в памяти: связный список линеен, но разбросан по памяти.
- Динамические структуры гибче, но платят памятью на указатели и временем на проход по цепочке.
- Сложность операций — ориентир для выбора: массив силен доступом по индексу, хеш-таблица — поиском по ключу, дерево — упорядоченным поиском по диапазону.
- Приведенные O-оценки типичные и имеют условия: O(1) хеш-таблицы и O(log n) дерева держатся только без массовых коллизий и при балансировке.
Где применяется / связь с практикой
Выбор структуры данных — повседневная работа при проектировании: от него зависит скорость поиска, объем памяти и читаемость кода. Умение сопоставить задачу и структуру, а затем оценить сложность операций, входит в базу для собеседований и для проектирования систем.
Освойте тему на практике
Системно разобрать структуры данных вместе с алгоритмами над ними помогает курс Алгоритмы и структуры данных: там разбирают не только сами структуры, но и оценку сложности и выбор под задачу. Прежде чем идти на полный курс, можно бесплатно посмотреть формат на открытых уроках и оценить, насколько тема заходит.
Смежные темы: Дерево как структура данных, Табличная структура данных, Типы данных в C.
FAQ
Чем структура данных отличается от типа данных? Тип данных описывает множество допустимых значений и операций (например, целое число). Структура данных — это способ организации набора таких значений и связей между ними (например, массив целых чисел). Тип — про одну ячейку, структура — про их организацию.
Абстрактный тип данных (АТД) — это то же, что структура данных? Нет. АТД (например, «стек») задает поведение и набор операций, не фиксируя реализацию. Структура данных — конкретная реализация этого поведения; один и тот же стек можно построить на массиве или на связном списке.
Полустатические структуры — обязательная категория? Нет, это термин из части русскоязычной литературы для стеков, очередей и строк с ограниченной переменной длиной. Во многих англоязычных источниках такой отдельной группы нет, а эти структуры относят к линейным динамическим. Это разница классификаций, а не разных объектов.
