Виды структур данных: классификация, примеры и код на Python
Основные виды структур данных простыми словами: массив, список, стек, очередь, хеш-таблица, дерево, куча, граф. Классификация, таблица сложности и примеры на Python.
Коротко
Структура данных — это способ хранить данные в памяти вместе с набором операций над ними. От выбора структуры зависит, сколько времени займут поиск, вставка и удаление.
| Структура | Вид | Сильная сторона | В Python |
|---|---|---|---|
| Массив | линейная | доступ по индексу за | list, array |
| Связный список | линейная | вставка и удаление по ссылке за | свой класс Node |
| Стек | линейная | последний пришёл — первый ушёл | list |
| Очередь, дек | линейная | первый пришёл — первый ушёл | collections.deque |
| Хеш-таблица | нелинейная | поиск по ключу в среднем за | dict, set |
| Дерево | нелинейная | иерархия и порядок, операции за | свой класс |
| Куча | нелинейная | минимум за | heapq |
| Граф | нелинейная | произвольные связи между объектами | dict списков |
Дальше — что вообще называют структурой данных, по каким признакам их делят и короткая справка по каждой со ссылкой на подробный разбор.
Понятие структуры данных
Данные в программе редко живут поодиночке. Список заказов, друзья пользователя, содержимое папки — это наборы значений, и между значениями есть отношения: «следующий», «вложен в», «связан с». Структура данных фиксирует две вещи:
- Как элементы лежат в памяти и как связаны между собой.
- Какие операции доступны и сколько они стоят.
Второй пункт важнее, чем кажется. Одни и те же числа можно положить и в массив, и в хеш-таблицу, но вопрос «есть ли среди них 42?» в первом случае потребует просмотра всех элементов, а во втором — одного обращения.
import time n = 1_000_000 as_list = list(range(n)) as_set = set(as_list) start = time.perf_counter() for _ in range(100): _ = (n - 1) in as_list list_time = time.perf_counter() - start start = time.perf_counter() for _ in range(100): _ = (n - 1) in as_set set_time = time.perf_counter() - start print(list_time > set_time * 100) # True
Данные одинаковые, код одинаковый, разница — на порядки. Поэтому структуры данных и идут первой темой на алгоритмических собеседованиях: алгоритм почти всегда упирается в то, где лежат данные.
Стоимость операций записывают в нотации «О большое»: — время не зависит от размера, — растёт пропорционально числу элементов, — растёт очень медленно. Если эти записи пока не читаются, начните со статьи про Big O.
Типы и структуры данных: в чём разница
Эти три понятия постоянно путают, в том числе на экзаменах.
Тип данных определяет, какие значения может принимать переменная и что с ними можно делать: int, float, bool, str. Простые типы хранят одно значение.
Структура данных собирает много значений в одно целое и задаёт способ их организации в памяти: массив, связный список, хеш-таблица.
Абстрактный тип данных (АТД) описывает только поведение, без реализации: «можно положить элемент, можно забрать последний положенный». Это контракт. Как он выполнен внутри — отдельный вопрос.
Стек и очередь — АТД. Массив и связный список — структуры данных, на которых их можно построить. Один и тот же стек реализуется и так, и так:
class ArrayStack: def __init__(self): self._items = [] def push(self, value): self._items.append(value) def pop(self): return self._items.pop() class Node: def __init__(self, value, next=None): self.value = value self.next = next class LinkedStack: def __init__(self): self._head = None def push(self, value): self._head = Node(value, self._head) def pop(self): node = self._head self._head = node.next return node.value for stack in (ArrayStack(), LinkedStack()): stack.push(1) stack.push(2) print(stack.pop(), stack.pop()) # 2 1
Снаружи оба класса ведут себя одинаково. Поэтому на вопрос «стек — это структура данных?» честный ответ такой: в быту да, строго — это абстрактный тип, а структура появляется, когда выбрана реализация.
Классификация структур данных
Единой официальной классификации нет: в учебниках структуры делят по разным признакам, и одна структура попадает сразу в несколько групп. Признаков, которые встречаются чаще всего, четыре.
Простые и составные
Простые (примитивные) — это базовые типы языка: целое число, вещественное, символ, булево значение. Составные собираются из простых: массив чисел, запись с полями, дерево узлов. Когда говорят «структуры данных в программировании», почти всегда имеют в виду составные.
Линейные и нелинейные
Главное деление, на нём держится большинство курсов.
- Линейные: элементы выстроены в цепочку, у каждого не больше одного предыдущего и одного следующего. Массив, связный список, стек, очередь, дек.
- Нелинейные: у элемента может быть несколько «соседей». Дерево (один родитель, много детей), граф (связи любые), хеш-таблица (элементы разложены по корзинам, порядка «следующий» нет).
Линейные структуры обходятся одним циклом от начала до конца. Для нелинейных нужен обход: в глубину или в ширину. Подробнее о первой группе — в статье про линейные структуры данных.
Статические и динамические
Статическая структура получает размер при создании и не меняет его: классический массив в C или Java. Динамическая растёт и сжимается во время работы: связный список, дерево, list в Python.
Питоновский list — это динамический массив: внутри лежит обычный массив с запасом, а когда запас кончается, элементы переезжают в блок побольше.
По способу размещения в памяти
- Непрерывные: элементы лежат подряд в одном блоке памяти. Массив, куча на массиве. Адрес элемента вычисляется арифметикой, поэтому доступ по индексу мгновенный.
- Ссылочные: каждый элемент хранится отдельно и держит ссылки на соседей. Связный список, дерево, граф. Вставка дешёвая, но до нужного элемента приходится идти по ссылкам.
Сводная картинка:
Структуры данных
├── Простые: int, float, bool, char
└── Составные
├── Линейные
│ ├── массив, динамический массив
│ ├── связный список
│ └── стек, очередь, дек
└── Нелинейные
├── хеш-таблица, множество
├── деревья: двоичное, BST, куча, префиксное
└── графы
Основные структуры данных
Массив
Набор элементов, лежащих в памяти подряд. Адрес элемента с номером i считается по формуле «начало + i × размер элемента», отсюда доступ за . Плата за это — вставка и удаление в середине: все элементы справа приходится сдвигать, это .
nums = [10, 20, 30, 40] print(nums[2]) # 30, доступ по индексу за O(1) nums.append(50) # в конец: O(1) в среднем nums.insert(0, 5) # в начало: O(n), сдвигаются все элементы print(nums) # [5, 10, 20, 30, 40, 50]
Берите массив, когда нужен доступ по номеру и данные в основном читаются или дописываются в конец. Подробно — в статье про массив.
Связный список
Цепочка узлов, где каждый узел хранит значение и ссылку на следующий. Узлы разбросаны по памяти, поэтому добраться до пятого элемента можно только через первые четыре: доступ по индексу — . Зато вставка или удаление рядом с уже найденным узлом — это перестановка пары ссылок, .
class ListNode: def __init__(self, value, next=None): self.value = value self.next = next head = ListNode(1, ListNode(2, ListNode(3))) # вставка после первого узла: меняем одну ссылку head.next = ListNode(99, head.next) node = head values = [] while node: values.append(node.value) node = node.next print(values) # [1, 99, 2, 3]
В прикладном коде на Python связный список нужен редко, но на собеседованиях это любимая тема: разворот, поиск цикла, слияние. Разбор — в статье про список как структуру данных.
Стек
Правило LIFO: последним пришёл — первым ушёл. Как стопка тарелок: кладём сверху, берём сверху. Операций две — push и pop, обе за .
def is_balanced(text): pairs = {')': '(', ']': '[', '}': '{'} stack = [] for ch in text: if ch in '([{': stack.append(ch) elif ch in pairs: if not stack or stack.pop() != pairs[ch]: return False return not stack print(is_balanced('{[()]}')) # True print(is_balanced('([)]')) # False
На стеке работают вызовы функций, отмена действий в редакторе, кнопка «назад» в браузере. Подробнее — про стек.
Очередь и дек
Очередь — правило FIFO: первым пришёл — первым ушёл, как в кассу. Добавляем в хвост, забираем из головы.
Частая ошибка новичков — делать очередь из list и забирать элементы через pop(0). Это на каждое извлечение, потому что массив сдвигается. Правильный инструмент — collections.deque:
from collections import deque queue = deque() queue.append('первый') queue.append('второй') queue.append('третий') print(queue.popleft()) # первый print(queue.popleft()) # второй print(len(queue)) # 1
deque — это дек, двусторонняя очередь: добавлять и забирать можно с обоих концов за . Очереди нужны для обхода в ширину, планировщиков задач, буферов. Читайте про очередь и отдельно про дек.
Хеш-таблица
Хранит пары «ключ — значение». Ключ прогоняется через хеш-функцию, результат превращается в номер ячейки массива. Поэтому поиск, вставка и удаление по ключу работают в среднем за — независимо от того, тысяча элементов в таблице или миллион.
В Python это dict, а set — та же таблица, только без значений.
def count_words(text): counts = {} for word in text.split(): counts[word] = counts.get(word, 0) + 1 return counts print(count_words('да нет да да')) # {'да': 3, 'нет': 1}
Ограничения: ключи должны быть хешируемыми (строка или кортеж подойдут, список — нет), а отсортированного порядка таблица не даёт. dict в Python помнит порядок вставки, но «найти ближайший ключ больше x» он не умеет. Как таблица устроена внутри и что такое коллизии — в статье про хеш-таблицы.
Дерево
Иерархическая структура: есть корень, у каждого узла — дети, циклов нет. Файловая система, DOM-дерево страницы, оргструктура компании — всё это деревья.
Самый частый вид — двоичное дерево, где детей не больше двух. Если добавить правило «слева меньше, справа больше», получится двоичное дерево поиска: в сбалансированном виде оно ищет, вставляет и удаляет за и при этом хранит ключи в отсортированном порядке.
class TreeNode: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right def height(node): if node is None: return 0 return 1 + max(height(node.left), height(node.right)) # 8 # / \ # 3 10 # / \ # 1 6 root = TreeNode(8, TreeNode(3, TreeNode(1), TreeNode(6)), TreeNode(10)) print(height(root)) # 3
Общий обзор — в статье про дерево как структуру данных, детали — про двоичное дерево. Для строк есть отдельная разновидность — префиксное дерево, на нём строят автодополнение.
Куча
Дерево с одним правилом: родитель не больше своих детей. Из-за этого минимум всегда лежит в корне и достаётся за , а вставка и извлечение стоят . Искать в куче произвольный элемент бессмысленно — она для этого не предназначена.
import heapq tasks = [] heapq.heappush(tasks, (3, 'ответить на письмо')) heapq.heappush(tasks, (1, 'починить прод')) heapq.heappush(tasks, (2, 'код-ревью')) print(heapq.heappop(tasks)) # (1, 'починить прод') print(heapq.heappop(tasks)) # (2, 'код-ревью')
На куче строят очередь с приоритетом, алгоритм Дейкстры, задачи вида «найди k самых больших». Любопытная деталь: логически это дерево, а физически — обычный массив. Почему так — в статье про двоичную кучу.
Граф
Самая общая структура: вершины и рёбра между ними, без ограничений. Карта дорог, подписки в соцсети, зависимости пакетов. Дерево — частный случай графа: связный и без циклов.
Обычно граф хранят как список смежности — словарь, где ключ — вершина, а значение — её соседи. Типовая операция — обход в ширину, он находит кратчайший путь по числу рёбер:
from collections import deque graph = { 'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': ['E'], 'E': [], } def shortest_path_length(graph, start, goal): queue = deque([(start, 0)]) visited = {start} while queue: vertex, distance = queue.popleft() if vertex == goal: return distance for neighbor in graph[vertex]: if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, distance + 1)) return -1 print(shortest_path_length(graph, 'A', 'E')) # 3
Обратите внимание: в одном примере работают сразу три структуры — хеш-таблица хранит граф, очередь задаёт порядок обхода, множество помнит посещённые вершины. В реальных задачах так почти всегда. Подробнее — про граф.
Сложность операций: сводная таблица
| Структура | Доступ по индексу | Поиск | Вставка | Удаление |
|---|---|---|---|---|
| Массив | , в конец * | |||
| Связный список | по ссылке | по ссылке | ||
| Стек | — | — | , только вершина | |
| Очередь | — | — | , только голова | |
| Хеш-таблица | — | в среднем | в среднем | в среднем |
| Сбалансированное дерево поиска | — | |||
| Куча | — | , минимум | , только минимум |
* В среднем, для динамического массива.
Две оговорки. У хеш-таблицы в худшем случае, когда много ключей попадает в одну ячейку, операции деградируют до . У дерева поиска без балансировки — тоже: если вставлять ключи по возрастанию, оно вырождается в связный список.
Как выбрать структуру данных
Идите от операции, которая выполняется чаще всего.
- Нужен доступ по номеру → массив.
- Нужно быстро проверять «есть ли элемент» или искать по ключу → хеш-таблица или множество.
- Нужен последний добавленный → стек.
- Нужна обработка в порядке поступления → очередь.
- Нужен минимум или максимум в постоянно меняющемся наборе → куча.
- Нужны отсортированный порядок и поиск ближайшего → сбалансированное дерево поиска или отсортированный массив с бинарным поиском.
- Данные вложены друг в друга → дерево.
- Связи между объектами произвольные → граф.
Если подходит несколько вариантов, берите самый простой. В девяти случаях из десяти в Python хватает list, dict и set.
Типичные ошибки
Путать list в Python со связным списком. Название обманывает: это динамический массив. Вставка в начало у него , а не .
Искать в списке внутри цикла. Проверка x in some_list — это . В цикле по n элементам выходит . Замена списка на set часто превращает решение, которое не проходит по времени, в проходящее.
Использовать list.pop(0) как очередь. Каждый вызов сдвигает весь массив. Нужен deque.popleft().
Считать, что хеш-таблица всегда лучше. Она не хранит порядок по значению ключа, расходует больше памяти и требует хешируемых ключей. Для диапазонных запросов и «ближайшего соседа» она бесполезна.
Называть двоичное дерево деревом поиска. Двоичное — это только про «не больше двух детей». Свойство «слева меньше, справа больше» — дополнительное правило, и у кучи, например, оно другое.
Что спрашивают на собеседованиях
Определения в чистом виде спрашивают редко. Обычно знание структур проверяют через задачу, где правильный выбор сокращает сложность:
- «Найдите два числа с заданной суммой» — перебор пар за заменяется хеш-таблицей и одним проходом.
- «Проверьте правильность скобок» — стек.
- «Разверните связный список» — работа со ссылками без дополнительной памяти.
- «Найдите k самых частых элементов» — хеш-таблица плюс куча.
- «Кратчайший путь в лабиринте» — граф и обход в ширину с очередью.
Устные вопросы тоже бывают: чем массив отличается от связного списка, как устроен dict, почему добавление в конец динамического массива считается , если иногда он копируется целиком. На каждый из них стоит уметь ответить в два-три предложения и назвать сложность основных операций.
Порядок изучения, который хорошо работает: массив → хеш-таблица → стек и очередь → связный список → деревья → куча → графы. Каждая следующая тема опирается на предыдущие, а первые три закрывают заметную часть задач начального уровня.