Структуры данных: абстрактные типы и как выбрать реализацию

Структура данных — это способ организовать набор значений в памяти вместе с операциями над ними: добавить, найти, удалить, обойти. Ключевое различие, которое дальше держим сквозь статью: абстрактный тип данных (АТД) описывает, какие операции доступны и как они себя ведут (контракт), а реализация описывает, как это устроено внутри и сколько стоит каждая операция. Один и тот же АТД можно построить на разных реализациях с разной сложностью.

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

АТД против реализации: развести сразу

Чтобы примеры дальше не казались противоречивыми, зафиксируем мини-словарь.

• АТД (контракт) — набор операций и их обещанное поведение. Пример: стек обещает push, pop, top и правило LIFO (последним вошел — первым вышел). Про память и скорость контракт молчит.
• Реализация — конкретное устройство в памяти. Тот же стек можно построить на массиве или на связном списке. Обе реализации выполняют контракт, но по-разному расходуют память и по-разному ведут себя при росте.
• Оценка сложности O — как растет число шагов операции при росте размера n. O(1) — не зависит от n; O(log n) — растет медленно; O(n) — линейно; O(n^2) — квадратично.

Практический вывод: выбирают сначала АТД (какие операции нужны), потом реализацию (какая дает нужную сложность). «Нужен стек» — это про контракт, «нужен массив» — уже про реализацию.

Массив и связный список: две базовые реализации

Почти все линейные структуры внутри опираются на одну из двух моделей хранения.

Массив (в динамическом варианте — список Python, ArrayList, vector) держит элементы в непрерывном участке памяти подряд. За счет этого доступ по индексу — O(1): адрес элемента вычисляется арифметикой от начала. Плата — вставка или удаление в середине сдвигает хвост, это O(n).

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

Минимальный узел односвязного списка на псевдокоде:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None   # ссылка на следующий узел, None - конец

# a -> b -> None
a = Node("a")
b = Node("b")
a.next = b
print(a.value, a.next.value)  # a b

Чтобы получить второй элемент, мы прошли по a.next, а не обратились по индексу: для n элементов это до n переходов, отсюда O(n) на доступ.

Стек и очередь: АТД поверх базовых структур

Стек — АТД с дисциплиной LIFO: доступен только верхний элемент. Операции push (положить наверх), pop (снять верхний), top (посмотреть верхний) — все O(1). Типичные применения: отмена действий (undo), разбор скобок, обход в глубину, стек вызовов функций.

stack = []
stack.append(1)      # push
stack.append(2)
stack.append(3)
print(stack.pop())   # 3 - последний вошел, первым вышел
print(stack.pop())   # 2
print(stack)         # [1]

Очередь — АТД с дисциплиной FIFO: элементы выходят в порядке прихода. Операции enqueue (добавить в конец) и dequeue (взять из начала). На обычном массиве взятие из начала было бы O(n) из-за сдвига, поэтому в Python берут deque (дек на блоках), где оба конца — O(1).

from collections import deque

q = deque()
q.append("a")        # enqueue
q.append("b")
q.append("c")
print(q.popleft())   # a - первый вошел, первым вышел
print(q.popleft())   # b
print(list(q))       # ['c']

Обратите внимание: стек и очередь — это контракты, а list и deque — реализации. Один и тот же стек можно собрать и на связном списке. Выбор реализации меняет сложность, но не поведение LIFO/FIFO.

Хеш-таблица: доступ по ключу

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

prices = {}
prices["milk"] = 80
prices["bread"] = 45
print(prices["milk"])     # 80 - доступ по ключу
print("eggs" in prices)   # False - проверка наличия

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

Дерево: иерархия и порядок

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

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

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

root = None
for k in [8, 3, 10, 1, 6]:
    root = insert(root, k)
print(root.key, root.left.key, root.right.key)  # 8 3 10

Границу назовем явно: O(log n) верна только для сбалансированного дерева. Если вставлять отсортированные ключи в наивный BST, он выродится в цепочку и даст O(n). Поэтому на практике берут самобалансирующиеся варианты (AVL, красно-черное дерево). Деревья лежат в основе индексов баз данных (там чаще B-дерево под диск) и сортированных множеств.

Граф: произвольные связи

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

Чаще всего граф хранят списком смежности — словарь, где ключ это вершина, а значение список ее соседей:

graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D"],
    "D": [],
}
print(graph["A"])   # ['B', 'C'] - соседи вершины A

Список смежности экономен для разреженных графов: память O(V + E). Альтернатива — матрица смежности O(V^2), удобна, когда ребер много. Обходят граф в ширину (BFS, на очереди) или в глубину (DFS, на стеке) — вот где базовые АТД возвращаются как инструмент.

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

Оценки — для типичных реализаций; среднее и худший случай различаются там, где это отмечено.

Как выбрать структуру: короткий алгоритм

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

1. Нужен доступ по позиции и предсказуемая память, вставки в основном в конец — динамический массив.
2. Часто вставляете и удаляете в середине, а доступ по индексу не нужен — связный список.
3. Обрабатываете в порядке LIFO (последнее — первым) — стек; в порядке FIFO (очередь задач, обход в ширину) — очередь.
4. Главное — быстрый поиск по ключу, порядок не важен — хеш-таблица.
5. Нужен быстрый поиск И упорядоченный обход или диапазоны — сбалансированное дерево.
6. Моделируете связи многие-ко-многим, ищете пути — граф.

Правило-ориентир: назовите две-три самые частые операции и по таблице выберите структуру, у которой именно они дешевые. Проигрыш на редкой операции обычно допустим.

Выводы

• АТД — это контракт (какие операции и их поведение), реализация — устройство в памяти и стоимость операций; выбирают сначала контракт, потом реализацию.
• Массив дает O(1) доступ по индексу, но O(n) на вставку в середину; связный список наоборот — O(1) вставка в точке, O(n) доступ.
• Стек (LIFO) и очередь (FIFO) — абстрактные типы, их можно строить на массиве или списке с O(1) на основные операции.
• Хеш-таблица дает O(1) в среднем, но без гарантии худшего случая и без порядка; сбалансированное дерево дает O(log n) с гарантией и с упорядоченным обходом.
• Выбор структуры ведут от самых частых операций задачи и их сложности по сводной таблице, а не от привычки.

Где применяется / связь с практикой

Структуры данных решают, будет ли программа работать за секунды или за минуты на тех же данных. Понимание разницы между АТД и реализацией и умение читать сложность O влияют на выбор архитектуры, на собеседования и на отладку узких мест. Дальше эти структуры соединяются с алгоритмами: обход графа, сортировки, поиск, динамическое программирование.

FAQ

Чем структура данных отличается от типа данных?
Скалярный тип (целое, символ, логический) описывает одно значение и операции над ним. Структура данных организует набор значений и связи между ними. В этой статье речь именно о композитных структурах, а не о примитивных типах языка.

Массив или список — что быстрее?
Зависит от операции. Массив быстрее на доступе по индексу (O(1) против O(n)), связный список — на вставке и удалении в уже найденной точке (O(1) против O(n)). Универсально «быстрее» нет, сравнивать нужно по частым операциям задачи.

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