ШПАРГАЛКА

Структуры данных

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

Структуры данных — это способы организации и хранения информации, от которых напрямую зависит скорость работы программы. Эта шпаргалка собирает ключевые структуры (массив, связный список, стек, очередь, дек, хеш-таблицу, множество, дерево, кучу и граф), их операции, асимптотическую сложность и готовые реализации на Python из стандартной библиотеки.

Как читать сложность (Big O)

O(1) — константа, не зависит от размера. O(log n) — логарифм, очень медленно растёт. O(n) — линейно. O(n log n) — типичная сортировка. O(n²) — квадрат, медленно. Ниже под каждой структурой указана сложность основных операций в худшем (а где важно — в усреднённом) случае.

Массив и динамический список (array, dynamic array)

Массив хранит элементы подряд в памяти, доступ по индексу — за O(1). В Python встроенный тип list — это динамический массив: он сам расширяется при добавлении. Минус массива — вставка и удаление в середину требуют сдвига элементов.

Когда применять

  • Нужен быстрый доступ по индексу и проход по порядку.
  • Добавление в основном в конец.
  • Не нужны частые вставки/удаления в начало или середину.

Сложность операций

ОперацияСложностьКомментарий
Доступ по индексу a[i]O(1)прямая адресация
Добавить в конец appendO(1)*амортизированно
Вставить в начало insert(0, x)O(n)сдвиг всех элементов
Удалить из серединыO(n)сдвиг хвоста
Поиск значения x in aO(n)перебор
 
a = [10, 20, 30]
a.append(40)        # [10, 20, 30, 40] — O(1)*
print(a[2])         # 30 — O(1)
a.insert(0, 5)      # [5, 10, 20, 30, 40] — O(n)
a.pop()             # удалить с конца — O(1)
a.pop(0)            # удалить с начала — O(n)
print(20 in a)      # поиск — O(n)

Связный список (singly / doubly linked list)

Связный список хранит элементы как узлы, каждый из которых ссылается на следующий (односвязный) или ещё и на предыдущий (двусвязный). Вставка и удаление узла — O(1), если ссылка на узел уже есть, но доступ по индексу медленный — O(n), нужно идти по цепочке.

Когда применять

  • Частые вставки/удаления в начало или середину при известной позиции.
  • Не нужен быстрый доступ по индексу.
  • В Python чаще берут collections.deque вместо ручного списка.

Сложность операций

ОперацияСложностьКомментарий
Доступ по индексуO(n)проход по узлам
Вставка в началоO(1)перецепить ссылку
Удаление узла (есть ссылка)O(1)в двусвязном
Поиск значенияO(n)перебор
 
class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

# Односвязный список 1 -> 2 -> 3
head = Node(1, Node(2, Node(3)))

# Вставка в начало — O(1)
head = Node(0, head)

# Обход — O(n)
node = head
while node:
    print(node.value, end=" ")  # 0 1 2 3
    node = node.next

Стек (stack, LIFO)

Стек работает по принципу LIFO (last in, first out) — последний пришёл, первый вышел. Как стопка тарелок: кладём и берём только сверху. Обе операции — O(1).

Когда применять

  • Откат действий (undo), история переходов.
  • Проверка скобок, обход в глубину (DFS), вычисление выражений.
  • Рекурсия по сути использует стек вызовов.

Сложность операций

ОперацияСложность
Положить push (append)O(1)
Снять popO(1)
Посмотреть верх peekO(1)
 
# Стек на обычном list
stack = []
stack.append("a")   # push
stack.append("b")
top = stack[-1]     # peek -> "b"
x = stack.pop()     # pop -> "b"
print(stack)        # ["a"]

Очередь (queue, FIFO)

Очередь работает по принципу FIFO (first in, first out) — первый пришёл, первый вышел. Как очередь в магазине. В Python для очереди берут collections.deque: добавление в конец и удаление из начала — O(1). Использовать обычный list.pop(0) нельзя — это O(n).

Когда применять

  • Обработка задач в порядке поступления.
  • Обход в ширину (BFS) по графу.
  • Буферы, пайплайны, планировщики.

Сложность операций

Операцияdequelist
Добавить в конецO(1)O(1)*
Взять из началаO(1)O(n)
 
from collections import deque

queue = deque()
queue.append("task1")    # в конец
queue.append("task2")
first = queue.popleft()  # из начала -> "task1" — O(1)
print(queue)             # deque(["task2"])

Дек (deque, двусторонняя очередь)

Дек (double-ended queue) — это очередь, в которую можно добавлять и из которой можно удалять с обоих концов за O(1). В Python это collections.deque — универсальный инструмент и для стека, и для очереди.

Когда применять

  • Нужны быстрые операции с обоих концов.
  • Скользящее окно (sliding window), история ограниченной длины (maxlen).

Сложность операций

ОперацияСложность
append / appendleftO(1)
pop / popleftO(1)
Доступ по индексу в серединеO(n)
 
from collections import deque

d = deque([1, 2, 3])
d.appendleft(0)   # [0, 1, 2, 3]
d.append(4)       # [0, 1, 2, 3, 4]
d.popleft()       # 0
d.pop()           # 4

# дек ограниченной длины
window = deque(maxlen=3)
for x in [1, 2, 3, 4]:
    window.append(x)
print(window)     # deque([2, 3, 4], maxlen=3)

Хеш-таблица (hash table / dict)

Хеш-таблица хранит пары ключ → значение и обеспечивает доступ по ключу в среднем за O(1). В Python это встроенный тип dict. Ключи должны быть хешируемыми (неизменяемыми): строки, числа, кортежи.

Когда применять

  • Нужен быстрый поиск/вставка/удаление по ключу.
  • Подсчёт частот, кеширование, индексы, группировка.

Сложность операций

ОперацияСреднееХудшее
Вставка d[k] = vO(1)O(n)
Поиск d[k]O(1)O(n)
Удаление del d[k]O(1)O(n)
Проверка k in dO(1)O(n)

Худший случай O(n) возникает крайне редко — при массовых коллизиях хешей.

from collections import Counter

d = {"apple": 3, "banana": 5}
d["cherry"] = 7          # вставка — O(1)
print(d["banana"])       # 5 — поиск O(1)
print("apple" in d)      # True
del d["apple"]           # удаление — O(1)

# Подсчёт частот через Counter
text = "abracadabra"
freq = Counter(text)
print(freq.most_common(2))  # [("a", 5), ("b", 2)]

Множество (set)

Множество хранит уникальные элементы без порядка и поддерживает проверку принадлежности за O(1). Под капотом — та же хеш-таблица. В Python это тип set (и неизменяемый frozenset).

Когда применять

  • Убрать дубликаты.
  • Быстро проверить «есть ли элемент».
  • Операции над множествами: объединение, пересечение, разность.

Сложность операций

ОперацияСложность
Добавить addO(1)
Проверка x in sO(1)
Удалить discardO(1)
Объединение / пересечениеO(n)
 
a = {1, 2, 3}
b = {3, 4, 5}

a.add(4)              # {1, 2, 3, 4}
print(2 in a)         # True — O(1)

print(a | b)          # объединение {1, 2, 3, 4, 5}
print(a & b)          # пересечение {3, 4}
print(a - b)          # разность {1, 2}

# Убрать дубликаты из списка
nums = [1, 1, 2, 3, 3, 3]
print(set(nums))      # {1, 2, 3}

Дерево и двоичное дерево поиска (binary tree, BST)

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

Когда применять

  • Нужны упорядоченные данные с быстрым поиском, вставкой и обходом по порядку.
  • Иерархии: файловая система, DOM, дерево решений.
  • Сбалансированные деревья (AVL, красно-чёрные) лежат в основе многих БД-индексов.

Сложность операций (BST)

ОперацияСбаланс.Худшее
ПоискO(log n)O(n)
ВставкаO(log n)O(n)
УдалениеO(log n)O(n)

Худший случай O(n) — когда дерево выродилось в «список» (узлы добавляли по возрастанию).

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert(root, value):
    if root is None:
        return TreeNode(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

def inorder(root):
    if root:
        inorder(root.left)
        print(root.value, end=" ")   # по возрастанию
        inorder(root.right)

root = None
for v in [5, 3, 8, 1, 4]:
    root = insert(root, v)
inorder(root)   # 1 3 4 5 8

Куча и очередь с приоритетом (heap, priority queue)

Куча (heap) — это двоичное дерево, где родитель всегда не больше детей (min-heap) или не меньше (max-heap). Это даёт мгновенный доступ к минимуму/максимуму за O(1) и извлечение за O(log n). На куче строят очередь с приоритетом. В Python — модуль heapq (min-heap на основе list).

Когда применять

  • Нужно постоянно доставать минимальный/максимальный элемент.
  • Алгоритм Дейкстры, A*, задачи «топ-K».
  • Планировщики задач по приоритету.

Сложность операций

ОперацияСложность
Посмотреть минимум heap[0]O(1)
Вставить heappushO(log n)
Извлечь минимум heappopO(log n)
Построить кучу heapifyO(n)
 
import heapq

heap = [5, 3, 8, 1]
heapq.heapify(heap)      # превратить в кучу — O(n)
heapq.heappush(heap, 2)  # вставка — O(log n)
print(heap[0])           # минимум -> 1 — O(1)
print(heapq.heappop(heap))  # извлечь минимум -> 1

# Очередь с приоритетом: (приоритет, задача)
pq = []
heapq.heappush(pq, (2, "отправить письмо"))
heapq.heappush(pq, (1, "срочный звонок"))
print(heapq.heappop(pq))  # (1, "срочный звонок")

# max-heap трюк: храним отрицательные значения
nums = [5, 3, 8, 1]
print(heapq.nlargest(2, nums))  # [8, 5]

Граф (graph): матрица и список смежности

Граф — это набор вершин (узлов) и рёбер (связей между ними). Графы бывают ориентированные/неориентированные, взвешенные/невзвешенные. Два главных способа хранения: матрица смежности и список смежности.

Когда применять

  • Любые сети связей: дороги, соцсети, зависимости, маршруты.
  • Поиск пути (BFS/DFS, Дейкстра), проверка связности, поиск циклов.

Два представления

КритерийМатрица смежностиСписок смежности
ПамятьO(V²)O(V + E)
Проверка ребра (u, v)O(1)O(степени u)
Перебор соседейO(V)O(степени u)
Лучше дляплотных графовразреженных графов

V — число вершин, E — число рёбер.

from collections import deque, defaultdict

# Список смежности (разреженный граф)
graph = defaultdict(list)
edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)   # неориентированный

# Матрица смежности (4 вершины)
n = 4
matrix = [[0] * n for _ in range(n)]
for u, v in edges:
    matrix[u][v] = 1
    matrix[v][u] = 1

# Обход в ширину (BFS) — O(V + E)
def bfs(start):
    visited = {start}
    q = deque([start])
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nxt in graph[node]:
            if nxt not in visited:
                visited.add(nxt)
                q.append(nxt)
    return order

print(bfs(0))   # порядок обхода от вершины 0

Сравнительная таблица структур

СтруктураДоступПоискВставкаУдалениеPython
Массив / списокO(1)O(n)O(n)O(n)list
Связный списокO(n)O(n)O(1)O(1)—
СтекO(n)O(n)O(1)O(1)list
ОчередьO(n)O(n)O(1)O(1)deque
ДекO(n)O(n)O(1)O(1)deque
Хеш-таблица—O(1)*O(1)*O(1)*dict
Множество—O(1)*O(1)*O(1)*set
BST (сбаланс.)O(log n)O(log n)O(log n)O(log n)—
КучаO(1) minO(n)O(log n)O(log n)heapq

* — усреднённая сложность. Прочерк означает, что операция для структуры не характерна.

Как выбрать структуру

  • Доступ по индексу и порядок → массив / list.
  • Быстрый поиск по ключу → хеш-таблица / dict.
  • Уникальность и членство → множество / set.
  • LIFO → стек (list); FIFO → очередь (deque).
  • Всегда нужен минимум/максимум → куча / heapq.
  • Упорядоченные данные с быстрым поиском → сбалансированное дерево (BST).
  • Сети связей и маршруты → граф (список смежности для разреженных, матрица — для плотных).

Смотри также шпаргалки по сложности алгоритмов и сортировкам, чтобы закрепить асимптотику на практике.

Поддержать проект