Виды структур данных: классификация, примеры и код на Python

Основные виды структур данных простыми словами: массив, список, стек, очередь, хеш-таблица, дерево, куча, граф. Классификация, таблица сложности и примеры на Python.

12 мин чтенияструктуры данных · основы · python

Коротко

Структура данных — это способ хранить данные в памяти вместе с набором операций над ними. От выбора структуры зависит, сколько времени займут поиск, вставка и удаление.

СтруктураВидСильная сторонаВ Python
Массивлинейнаядоступ по индексу за O(1)O(1)list, array
Связный списоклинейнаявставка и удаление по ссылке за O(1)O(1)свой класс Node
Стеклинейнаяпоследний пришёл — первый ушёлlist
Очередь, деклинейнаяпервый пришёл — первый ушёлcollections.deque
Хеш-таблицанелинейнаяпоиск по ключу в среднем за O(1)O(1)dict, set
Деревонелинейнаяиерархия и порядок, операции за O(log⁡n)O(\log n)свой класс
Кучанелинейнаяминимум за O(1)O(1)heapq
Графнелинейнаяпроизвольные связи между объектамиdict списков

Дальше — что вообще называют структурой данных, по каким признакам их делят и короткая справка по каждой со ссылкой на подробный разбор.

Понятие структуры данных

Данные в программе редко живут поодиночке. Список заказов, друзья пользователя, содержимое папки — это наборы значений, и между значениями есть отношения: «следующий», «вложен в», «связан с». Структура данных фиксирует две вещи:

  1. Как элементы лежат в памяти и как связаны между собой.
  2. Какие операции доступны и сколько они стоят.

Второй пункт важнее, чем кажется. Одни и те же числа можно положить и в массив, и в хеш-таблицу, но вопрос «есть ли среди них 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

Данные одинаковые, код одинаковый, разница — на порядки. Поэтому структуры данных и идут первой темой на алгоритмических собеседованиях: алгоритм почти всегда упирается в то, где лежат данные.

Стоимость операций записывают в нотации «О большое»: O(1)O(1) — время не зависит от размера, O(n)O(n) — растёт пропорционально числу элементов, O(log⁡n)O(\log n) — растёт очень медленно. Если эти записи пока не читаются, начните со статьи про 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 × размер элемента», отсюда доступ за O(1)O(1). Плата за это — вставка и удаление в середине: все элементы справа приходится сдвигать, это O(n)O(n).

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]

Берите массив, когда нужен доступ по номеру и данные в основном читаются или дописываются в конец. Подробно — в статье про массив.

Связный список

Цепочка узлов, где каждый узел хранит значение и ссылку на следующий. Узлы разбросаны по памяти, поэтому добраться до пятого элемента можно только через первые четыре: доступ по индексу — O(n)O(n). Зато вставка или удаление рядом с уже найденным узлом — это перестановка пары ссылок, O(1)O(1).

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, обе за O(1)O(1).

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). Это O(n)O(n) на каждое извлечение, потому что массив сдвигается. Правильный инструмент — 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 — это дек, двусторонняя очередь: добавлять и забирать можно с обоих концов за O(1)O(1). Очереди нужны для обхода в ширину, планировщиков задач, буферов. Читайте про очередь и отдельно про дек.

Хеш-таблица

Хранит пары «ключ — значение». Ключ прогоняется через хеш-функцию, результат превращается в номер ячейки массива. Поэтому поиск, вставка и удаление по ключу работают в среднем за O(1)O(1) — независимо от того, тысяча элементов в таблице или миллион.

В 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-дерево страницы, оргструктура компании — всё это деревья.

Самый частый вид — двоичное дерево, где детей не больше двух. Если добавить правило «слева меньше, справа больше», получится двоичное дерево поиска: в сбалансированном виде оно ищет, вставляет и удаляет за O(log⁡n)O(\log n) и при этом хранит ключи в отсортированном порядке.

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

Общий обзор — в статье про дерево как структуру данных, детали — про двоичное дерево. Для строк есть отдельная разновидность — префиксное дерево, на нём строят автодополнение.

Куча

Дерево с одним правилом: родитель не больше своих детей. Из-за этого минимум всегда лежит в корне и достаётся за O(1)O(1), а вставка и извлечение стоят O(log⁡n)O(\log n). Искать в куче произвольный элемент бессмысленно — она для этого не предназначена.

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

Обратите внимание: в одном примере работают сразу три структуры — хеш-таблица хранит граф, очередь задаёт порядок обхода, множество помнит посещённые вершины. В реальных задачах так почти всегда. Подробнее — про граф.

Сложность операций: сводная таблица

СтруктураДоступ по индексуПоискВставкаУдаление
МассивO(1)O(1)O(n)O(n)O(n)O(n), в конец O(1)O(1)*O(n)O(n)
Связный списокO(n)O(n)O(n)O(n)O(1)O(1) по ссылкеO(1)O(1) по ссылке
Стек——O(1)O(1)O(1)O(1), только вершина
Очередь——O(1)O(1)O(1)O(1), только голова
Хеш-таблица—O(1)O(1) в среднемO(1)O(1) в среднемO(1)O(1) в среднем
Сбалансированное дерево поиска—O(log⁡n)O(\log n)O(log⁡n)O(\log n)O(log⁡n)O(\log n)
Куча—O(n)O(n), минимум O(1)O(1)O(log⁡n)O(\log n)O(log⁡n)O(\log n), только минимум

* В среднем, для динамического массива.

Две оговорки. У хеш-таблицы в худшем случае, когда много ключей попадает в одну ячейку, операции деградируют до O(n)O(n). У дерева поиска без балансировки — тоже: если вставлять ключи по возрастанию, оно вырождается в связный список.

Как выбрать структуру данных

Идите от операции, которая выполняется чаще всего.

  • Нужен доступ по номеру → массив.
  • Нужно быстро проверять «есть ли элемент» или искать по ключу → хеш-таблица или множество.
  • Нужен последний добавленный → стек.
  • Нужна обработка в порядке поступления → очередь.
  • Нужен минимум или максимум в постоянно меняющемся наборе → куча.
  • Нужны отсортированный порядок и поиск ближайшего → сбалансированное дерево поиска или отсортированный массив с бинарным поиском.
  • Данные вложены друг в друга → дерево.
  • Связи между объектами произвольные → граф.

Если подходит несколько вариантов, берите самый простой. В девяти случаях из десяти в Python хватает list, dict и set.

Типичные ошибки

Путать list в Python со связным списком. Название обманывает: это динамический массив. Вставка в начало у него O(n)O(n), а не O(1)O(1).

Искать в списке внутри цикла. Проверка x in some_list — это O(n)O(n). В цикле по n элементам выходит O(n2)O(n^2). Замена списка на set часто превращает решение, которое не проходит по времени, в проходящее.

Использовать list.pop(0) как очередь. Каждый вызов сдвигает весь массив. Нужен deque.popleft().

Считать, что хеш-таблица всегда лучше. Она не хранит порядок по значению ключа, расходует больше памяти и требует хешируемых ключей. Для диапазонных запросов и «ближайшего соседа» она бесполезна.

Называть двоичное дерево деревом поиска. Двоичное — это только про «не больше двух детей». Свойство «слева меньше, справа больше» — дополнительное правило, и у кучи, например, оно другое.

Что спрашивают на собеседованиях

Определения в чистом виде спрашивают редко. Обычно знание структур проверяют через задачу, где правильный выбор сокращает сложность:

  • «Найдите два числа с заданной суммой» — перебор пар за O(n2)O(n^2) заменяется хеш-таблицей и одним проходом.
  • «Проверьте правильность скобок» — стек.
  • «Разверните связный список» — работа со ссылками без дополнительной памяти.
  • «Найдите k самых частых элементов» — хеш-таблица плюс куча.
  • «Кратчайший путь в лабиринте» — граф и обход в ширину с очередью.

Устные вопросы тоже бывают: чем массив отличается от связного списка, как устроен dict, почему добавление в конец динамического массива считается O(1)O(1), если иногда он копируется целиком. На каждый из них стоит уметь ответить в два-три предложения и назвать сложность основных операций.

Порядок изучения, который хорошо работает: массив → хеш-таблица → стек и очередь → связный список → деревья → куча → графы. Каждая следующая тема опирается на предыдущие, а первые три закрывают заметную часть задач начального уровня.

Потренироваться в спокойной обстановке

Все задачи

Читать дальше

Все статьи
Алгоритмы и структуры данныхОчередь (queue): структура данных FIFO, операции и реализация на PythonОчередь как структура данных простыми словами: принцип FIFO, операции за O(1), почему list.pop(0) медленный, collections.deque, кольцевая очередь и применение в BFS и планировщиках.Алгоритмы и структуры данныхГраф как структура данных: матрица смежности, список смежности и список рёбер на PythonЧто такое граф в программировании: вершины и рёбра, ориентированный, неориентированный и взвешенный граф. Три представления графа в памяти с кодом на Python и сравнением по памяти и скорости.Алгоритмы и структуры данныхБинарное дерево: что это, виды, листья, полное и сбалансированное деревоБинарное дерево простыми словами: корень, узлы и листья, высота, виды деревьев (строгое, полное, совершенное, сбалансированное, вырожденное) и построение на Python с рабочим кодом.