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

Структуры данных — это способы организации и хранения информации для эффективного доступа и модификации. Выбор правильной структуры данных может ускорить программу в сотни раз. Это знание не зависит от языка — массивы в C++, Python, Java или Go работают по одним и тем же принципам.

1. Линейные структуры 📏¶

Массивы (Arrays)¶

Определение: Непрерывный блок памяти, хранящий элементы одного типа.

Характеристики:

┌────────────────────┬───────────┬────────────────────────────────────────────────────┐
│ Операция           │ Сложность │ Описание                                           │
├────────────────────┼───────────┼────────────────────────────────────────────────────┤
│ Доступ по индексу  │ **O(1)**  │ Мгновенно: `address = base + index * element_size` │
│ Поиск              │ O(n)      │ Нужно перебрать все элементы                       │
│ Вставка в конец    │ O(1)*     │ Амортизированно (если есть место)                  │
│ Вставка в середину │ **O(n)**  │ Нужно сдвинуть все элементы справа                 │
│ Удаление           │ **O(n)**  │ Нужно сдвинуть элементы и заполнить дыру           │
└────────────────────┴───────────┴────────────────────────────────────────────────────┘

Плюсы: - ✅ Быстрый доступ по индексу - ✅ Компактное хранение (нет накладных расходов на указатели) - ✅ Кэш-локальность (элементы лежат рядом в памяти)

Минусы: - ❌ Фиксированный размер (в статических массивах) - ❌ Дорогая вставка/удаление в середине

Пример использования: Хранение пикселей изображения, буфер аудио, матрицы.

# Python: списки — динамические массивы
arr = [10, 20, 30, 40, 50]
print(arr[2])      # O(1): 30
arr.insert(2, 25)  # O(n): сдвиг элементов [10, 20, 25, 30, 40, 50]

Связные списки (Linked Lists)¶

Определение: Элементы (узлы) хранятся в произвольных местах памяти, каждый содержит данные и указатель на следующий узел.

Виды: - Односвязный: Каждый узел → следующий. - Двусвязный: Узел → следующий + предыдущий. - Циклический: Последний узел → первый.

Характеристики:

┌────────────────────┬───────────┬─────────────────────────────────────────┐
│ Операция           │ Сложность │ Описание                                │
├────────────────────┼───────────┼─────────────────────────────────────────┤
│ Доступ по индексу  │ **O(n)**  │ Нужно пройти от головы до элемента      │
│ Поиск              │ O(n)      │ Перебор всех узлов                      │
│ Вставка в начало   │ **O(1)**  │ Изменить указатель головы               │
│ Вставка в середину │ O(1)*     │ Если известен узел перед точкой вставки │
│ Удаление           │ O(1)*     │ Если известен узел                      │
└────────────────────┴───────────┴─────────────────────────────────────────┘

Плюсы: - ✅ Динамический размер (растет/сжимается при необходимости) - ✅ Быстрая вставка/удаление (без сдвига элементов) - ✅ Нет фрагментации памяти

Минусы: - ❌ Медленный доступ по индексу - ❌ Дополнительные расходы на указатели (2x-3x больше памяти) - ❌ Плохая кэш-локальность (узлы разбросаны в памяти)

Пример использования: Реализация стеков, очередей, undo/redo в редакторах.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Вставка в начало: O(1)
new_node = Node(100)
new_node.next = head
head = new_node

Стеки (Stacks)¶

Определение: Структура LIFO (Last In, First Out) — последний пришел, первый ушел.

Операции: - push(x) — добавить элемент на вершину. O(1). - pop() — удалить и вернуть верхний элемент. O(1). - peek() — посмотреть верхний элемент без удаления. O(1).

Применение: - Вызов функций (стек вызовов). - Отмена действий (Ctrl+Z). - Проверка скобочных последовательностей. - DFS (поиск в глубину).

stack = []
stack.append(1)   # push
stack.append(2)
top = stack.pop() # pop → 2

Задача: Проверка правильности скобочной последовательности.

def is_valid(s: str) -> bool:
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in mapping:
            top = stack.pop() if stack else '#'
            if mapping[char] != top:
                return False
        else:
            stack.append(char)
    return not stack

Очереди (Queues)¶

Определение: Структура FIFO (First In, First Out) — первый пришел, первый ушел.

Операции: - enqueue(x) — добавить в хвост. O(1). - dequeue() — удалить из головы. O(1). - front() — посмотреть первый элемент. O(1).

Варианты: - Обычная очередь: FIFO. - Дек (Deque): Двусторонняя очередь, вставка/удаление с обоих концов. - Приоритетная очередь: Элементы извлекаются по приоритету (реализуется через кучу).

Применение: - Обработка запросов к серверу. - Печать документов. - BFS (поиск в ширину). - Буферизация потоков данных.

from collections import deque
queue = deque()
queue.append(1)      # enqueue
queue.append(2)
first = queue.popleft()  # dequeue → 1

2. Иерархические структуры 🌳¶

Деревья (Trees)¶

Определение: Иерархическая структура из узлов (вершин), соединенных ребрами. Один корневой узел, каждый узел имеет 0 или более дочерних.

Термины: - Корень (Root): Верхний узел без родителя. - Лист (Leaf): Узел без детей. - Высота: Максимальное количество ребер от корня до листа. - Глубина: Количество ребер от корня до данного узла.

Бинарное дерево поиска (BST — Binary Search Tree)¶

Свойство: Для каждого узла: - Все значения в левом поддереве < значения узла. - Все значения в правом поддереве > значения узла.

Характеристики:

┌──────────┬─────────────────────┬───────────────────────────────┐
│ Операция │ Сложность (средняя) │ Сложность (худшая)            │
├──────────┼─────────────────────┼───────────────────────────────┤
│ Поиск    │ O(log n)            │ **O(n)** (вырожденное дерево) │
│ Вставка  │ O(log n)            │ O(n)                          │
│ Удаление │ O(log n)            │ O(n)                          │
└──────────┴─────────────────────┴───────────────────────────────┘

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

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

def search(root, target):
    if not root or root.val == target:
        return root
    if target < root.val:
        return search(root.left, target)
    return search(root.right, target)

Сбалансированные деревья¶

Решают проблему вырождения BST, поддерживая высоту O(log n).

┌──────────────────────────┬─────────────────────────────────────────┬──────────────────────────────────────────────────┐
│ Тип                      │ Принцип балансировки                    │ Применение                                       │
├──────────────────────────┼─────────────────────────────────────────┼──────────────────────────────────────────────────┤
│ **AVL-дерево**           │ Разница высот поддеревьев ≤ 1           │ Там, где много поисков (словари)                 │
│ **Красно-черное дерево** │ Правила окраски узлов (красный/черный)  │ STL (C++), TreeMap (Java), ассоциативные массивы │
│ **B-дерево**             │ Множественные дети на узел (для дисков) │ Базы данных, файловые системы                    │
│ **Дерево отрезков**      │ Хранение агрегатов на отрезках          │ Запросы диапазона (сумма, мин, макс)             │
└──────────────────────────┴─────────────────────────────────────────┴──────────────────────────────────────────────────┘

Применение деревьев: - Индексы в базах данных (B-деревья). - Автодополнение (Trie, префиксное дерево). - Сжатие данных (Huffman tree). - Маршрутизация в сетях (routing tables).

3. Хэш-таблицы (Hash Tables) ⚡¶

Определение: Структура, отображающая ключи в значения через хэш-функцию. Обеспечивает быстрый поиск, вставку и удаление.

Принцип работы: 1. Вычисляется хэш ключа: index = hash(key) % capacity. 2. Значение сохраняется в ячейку table[index].

Характеристики:

┌──────────┬─────────────────────┬───────────────────────┐
│ Операция │ Сложность (средняя) │ Сложность (худшая)    │
├──────────┼─────────────────────┼───────────────────────┤
│ Поиск    │ **O(1)**            │ O(n) (много коллизий) │
│ Вставка  │ **O(1)**            │ O(n)                  │
│ Удаление │ **O(1)**            │ O(n)                  │
└──────────┴─────────────────────┴───────────────────────┘

Коллизии: Ситуация, когда два ключа дают одинаковый хэш.

Методы разрешения коллизий: 1. Метод цепочек: В каждой ячейке — связный список (или дерево) элементов. 2. Открытая адресация: При коллизии ищем следующую свободную ячейку (линейный пробег, квадратичный, двойное хэширование).

Требования к хэш-функции: - Детерминированность: hash(x) всегда одинаков для одного x. - Равномерность: Хэши распределяются равномерно по таблице. - Эффективность: Быстрое вычисление.

Пример (Python dict):

d = {'name': 'Alice', 'age': 25, 'city': 'Moscow'}
print(d['name'])  # O(1): Alice
d['age'] = 26     # O(1): обновление

Применение: - Словари, ассоциативные массивы. - Кэширование (memoization). - Подсчет частоты элементов. - Проверка дубликатов. - Реализация множеств (set).

4. Продвинутые структуры 🚀¶

Куча (Heap)¶

Определение: Бинарное дерево, удовлетворяющее свойству кучи: - Max-heap: Каждый узел ≥ своих детей (корень — максимум). - Min-heap: Каждый узел ≤ своих детей (корень — минимум).

Реализация: Обычно массивом. Для узла i: - Левый ребенок: 2*i + 1 - Правый ребенок: 2*i + 2 - Родитель: (i-1) // 2

Характеристики:

┌─────────────────────┬───────────┐
│ Операция            │ Сложность │
├─────────────────────┼───────────┤
│ Вставка             │ O(log n)  │
│ Извлечение мин/макс │ O(log n)  │
│ Получение мин/макс  │ **O(1)**  │
└─────────────────────┴───────────┘

Применение: - Приоритетные очереди. - Алгоритм Дейкстры (кратчайший путь). - Сортировка Heap Sort. - Поиск K наибольших/наименьших элементов.

import heapq
heap = []
heapq.heappush(heap, 10)
heapq.heappush(heap, 5)
heapq.heappush(heap, 20)
min_val = heapq.heappop(heap)  # 5

Trie (Префиксное дерево)¶

Определение: Дерево для хранения строк, где каждый узел — символ, а путь от корня до узла — строка.

Применение: - Автодополнение (Google Search). - Проверка орфографии. - IP-маршрутизация (longest prefix match). - Словари для игр (Scrabble).

       (root)
      /   |   \
     c    a    t
    / \   |    |
   a   h  r    e
  /     \|    |
 t      t p   a
```text
┌──┐
│  │
├──┤
└──┘

s r

*Слова: cat, cats, chat, art, car, tea, tear*

### Skip List (Список с пропусками)

**Определение:** probabilistic структура, альтернатива сбалансированным деревьям. Многоуровневый связный список с "экспресс-полосами".

**Сложность:** O(log n) для поиска, вставки, удаления.

**Преимущества перед AVL/Red-Black:**
- Проще в реализации.
- Легче распараллеливается.
- Используется в Redis, LevelDB.

---

## 📊 Сравнительная таблица структур данных

```text
┌─────────────────────┬──────────┬──────────┬──────────┬──────────┬───────────────┬───────────────────────────────┐
│ Структура           │ Доступ   │ Поиск    │ Вставка  │ Удаление │ Память        │ Лучшее применение             │
├─────────────────────┼──────────┼──────────┼──────────┼──────────┼───────────────┼───────────────────────────────┤
│ **Массив**          │ O(1)     │ O(n)     │ O(n)     │ O(n)     │ Низкая        │ Индексный доступ, кэш-френдли │
│ **Связный список**  │ O(n)     │ O(n)     │ O(1)*    │ O(1)*    │ Средняя       │ Частые вставки/удаления       │
│ **Стек**            │ O(n)     │ O(n)     │ O(1)     │ O(1)     │ Низкая        │ LIFO, undo, DFS               │
│ **Очередь**         │ O(n)     │ O(n)     │ O(1)     │ O(1)     │ Низкая        │ FIFO, буферы, BFS             │
│ **BST**             │ O(log n) │ O(log n) │ O(log n) │ O(log n) │ Средняя       │ Упорядоченные данные          │
│ **AVL / Red-Black** │ O(log n) │ O(log n) │ O(log n) │ O(log n) │ Высокая       │ Гарантированный log n         │
│ **Хэш-таблица**     │ N/A      │ O(1)     │ O(1)     │ O(1)     │ Высокая       │ Быстрый поиск по ключу        │
│ **Куча**            │ N/A      │ O(n)     │ O(log n) │ O(log n) │ Низкая        │ Приоритеты, min/max           │
│ **Trie**            │ O(m)     │ O(m)     │ O(m)     │ O(m)     │ Очень высокая │ Строки, префиксы              │
└─────────────────────┴──────────┴──────────┴──────────┴──────────┴───────────────┴───────────────────────────────┘

*m = длина ключа/строки

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

Задайте себе вопросы:

Нужен ли быстрый доступ по индексу? → Массив.
Частые вставки/удаления в середине? → Связный список.
Нужен порядок LIFO или FIFO? → Стек или очередь.
Быстрый поиск по ключу? → Хэш-таблица.
Нужно хранить данные отсортированными? → BST / AVL / Red-Black.
Работа со строками и префиксами? → Trie.
Нужен приоритетный доступ (min/max)? → Куча.
Ограничения по памяти? → Избегайте структур с указателями (списки, деревья).

Золотое правило: Нет "лучшей" структуры данных. Есть та, которая лучше подходит для вашей задачи.

💡 Практическое применение¶

Базы данных: B-деревья для индексов, хэш-таблицы для JOIN.
Компиляторы: Символьные таблицы (хэш-таблицы), AST (деревья).
Сети: Таблицы маршрутизации (Trie, хэш-таблицы).
OS: Планировщик процессов (приоритетная очередь), управление памятью (списки свободных блоков).
Поисковики: Инвертированные индексы (хэш-таблицы + списки), автодополнение (Trie).
Кэши: LRU cache (хэш-таблица + двусвязный список).

Запомните: Глубокое понимание структур данных отличает junior от senior разработчика. Вы не будете изобретать велосипед, но сможете выбрать правильный инструмент для задачи.