# Правильная форма делает сложное простым

Экспресс-курс о структурах данных и Big-O. 16 понятий — Data Structure, Big-O, Array, Hash Map, Set, Stack, Queue, Tree, Graph и другие — у каждого английское название, схема, карточка с примером и ценой и связи с остальными. В конце — шпаргалка: какая структура для какой операции.

- **Author:** Фёдор Чищин
- **Level:** intro
- **Reading time:** ~30 минут чтения
- **Published:** 2026-06-13
- **Source:** https://fedorthinks.com/ru/learn/data-structures-express

---

## 1. Зачем нужна структура

До конкретных структур — идея, общая для всех. Структура данных — не академия. Это тот самый выбор, который чаще всего решает, будет код быстрым или мучительно медленным.

### Карта курса: 16 понятий в шести группах

> Карта метро: сначала видишь все линии, потом едешь по станциям.

Сверху — три базовые идеи: **Data Structure**, **Trade-off** и **Big-O**. Дальше шесть групп: формы роста Big-O, массив, хеш-таблица и множество, структуры с порядком (стек и очередь), структуры с формой (дерево и граф) и, наконец, как всё это выбирать на практике.

_Diagram: Три базовые идеи сверху и шесть групп — по ним идут главы 2–7._

### Как читать курс

> Паспорт: одинаковые поля у всех, поэтому их легко сравнивать.

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

### Data Structure — структура данных

> Ящик с инструментами, где у каждого своё гнездо, против мешка, куда всё свалено. Инструменты те же, но из ящика нужный берёшь сразу, а в мешке каждый раз роешься.

**Структура данных (data structure)** — это способ расположить данные в памяти. Разные расположения делают быстрыми разные операции: одно отлично ищет по имени, другое держит порядок, третье всегда отдаёт самый свежий элемент. Вся игра — подобрать структуру под **то, что ты делаешь чаще всего**.

Та же задача бывает тривиальной или почти невозможной — смотря как лежат данные. Найти слово в отсортированном словаре — секунды; в тех же словах, сваленных как попало, — целый день. Поэтому удивительно много «сделай быстрее» на деле значит «храни в правильной форме». **Структура и есть решение.**

_Diagram: Одни и те же данные: в куче ищем перебором, в таблице по id — прыгаем сразу._

#### Data Structure (структура данных)

- **Что это:** Способ расположить данные в памяти под определённые операции.
- **Как работает:** Расположение заранее решает, какие операции будут дешёвыми, а какие — дорогими.
- **Пример:** Найти пользователя по ID: в одной структуре — мгновенно, в другой — перебор всех.
- **Цена:** Неверный выбор не лечится «хитрой оптимизацией» потом.
- **Связи:** Скорость структур сравнивают через **Big-O**; выбирают через **Trade-off**.

### Trade-off — каждая структура это размен

> Спорткар и грузовик для переезда — оба транспорт. Ты не спрашиваешь, какой лучше; ты спрашиваешь: лучше для чего?

Ни одна структура не лучшая во всём. Одна даёт мгновенный поиск, но без порядка; другая держит порядок, но медленно ищет; третья быстро добавляет, но медленно находит что-то внутри. Это и есть **trade-off (размен)**: сила в одной операции оплачена слабостью в другой. Бесплатного обеда нет — твоя работа выбрать размен, который подходит твоему случаю.

_Diagram: У каждой структуры своя сильная и своя слабая сторона._

#### Trade-off (размен, компромисс)

- **Что это:** Сила структуры в одной операции всегда стоит слабости в другой.
- **Пример:** **Hash Map** ищет по ключу мгновенно, но не хранит порядок; **Array** хранит порядок, но медленно ищет по значению.
- **Когда думать:** Каждый раз, когда выбираешь, где хранить данные: что я делаю часто, а что редко?
- **Связи:** Размен меряется в **Big-O** — у каждой операции своя «форма».

> **Вопрос рамки:** «Какую операцию я буду делать над этими данными чаще всего — искать, держать порядок, добавлять и удалять — и какая структура делает именно её быстрой, даже ценой остального?»

> Структура данных раскладывает данные так, чтобы частые операции были быстрыми. Правильная форма делает сложную задачу лёгкой — и каждая структура платит слабостью в одном за силу в другом.

## 2. Big-O: как растёт цена

Чтобы сравнивать структуры, нужен язык скорости, который не зависит от компьютера. Big-O и есть этот язык: он меряет, как растёт работа, когда растут данные.

### Big-O notation — рост, а не секунды

> Вопрос не «сколько длится одна доставка», а «как меняется общее время, когда в маршруте не десять остановок, а десять тысяч». Форма роста, а не показания секундомера.

Нотация **Big-O** описывает, как растёт цена операции, когда растёт объём данных — его обозначают **n**. Она не смотрит на миллисекунды и конкретную машину, а ловит _форму_: удвоили данные — работа удвоилась, учетверилась или почти не изменилась? Эта форма и решает, останется ли код быстрым на больших данных. Поэтому Big-O — способ сравнить подходы, даже не запуская их.

_Diagram: Чем больше n, тем сильнее расходятся формы: O(1) и O(log n) почти лежат, O(n²) уходит вверх._

#### Big-O notation («О большое», асимптотическая сложность)

- **Что это:** Описание того, как растёт работа при росте данных **n**.
- **Как работает:** Отбрасываем точные секунды и детали железа, оставляем форму роста.
- **Пример:** «Поиск по массиву — O(n)»: в десять раз больше элементов — примерно в десять раз больше работы.
- **Подвох:** Не говорит, сколько секунд займёт; говорит, как это масштабируется.
- **Связи:** Основные формы — в **Complexity classes**.

### Complexity classes — формы от отличной до ужасной

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

Несколько форм покрывают почти весь код:

- **O(1)** — константа: время одно и то же при любом размере (взять элемент по индексу).
- **O(log n)** — логарифм: почти не растёт, даже когда данных становится очень много (каждый шаг делит поиск пополам).
- **O(n)** — линейная: растёт вместе с данными (просмотреть весь список).
- **O(n²)** — квадратичная: взрывается (сравнить каждый элемент с каждым). Классика «в тестах нормально, в проде умирает».

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

_Diagram: На тестовых десяти элементах все формы похожи; на миллиарде — пропасть._

#### Complexity classes (O(1), O(log n), O(n), O(n²))

- **Что это:** Названия типичных форм роста работы.
- **Пример:** Индекс в массиве — O(1); поиск в сбалансированном дереве — O(log n); перебор списка — O(n); цикл в цикле — O(n²).
- **Подвох:** O(n²) прекрасно работает на тестовых данных и молотит минутами на миллионе записей.
- **Правило:** O(1) и O(log n) переживают масштаб; O(n) честная; O(n²) — сигнал тревоги.
- **Связи:** **Map before loop** — главный способ превратить O(n²) в O(n).

> **Вопрос Big-O:** «Когда эти данные станут большими, какая форма у этой операции — работа стоит на месте, растёт вместе с данными или взрывается — и переживёт ли она реальный размер?»

> Big-O меряет, как растёт работа вместе с данными, а не секунды. O(1) и O(log n) переживают масштаб; O(n) честная; O(n²) нормальна в тестах и умирает в проде.

## 3. Array — массив

Самая базовая структура — массив, или список: элементы по порядку. Если точно знать, в чём он быстр и в чём медленен, всё остальное легко сравнивать с ним.

### Array — упорядоченная нумерованная последовательность

> Ряд пронумерованных шкафчиков: вещи стоят по порядку, у каждой свой номер — 0, 1, 2… — и к любому шкафчику можно подойти сразу по номеру.

**Массив (array, list)** хранит элементы по порядку, каждый на своей позиции — **индексе (index)**, начиная с 0. Элементы лежат подряд, в известном месте памяти, поэтому прыгнуть к любой позиции по индексу — мгновенно, **O(1)**. Массив — выбор по умолчанию для «кучи вещей по порядку», а доступ по позиции — его суперсила.

Но есть цена. Добавить или убрать элемент в _конце_ — дёшево. А вставка или удаление в _середине_ сдвигает всё, что после, чтобы сохранить порядок и нумерацию, — это **O(n)**.

_Diagram: Знаешь индекс — сразу открываешь нужный шкафчик._

_Diagram: Вставка в середину сдвигает всех, кто после; добавление в конец — дёшево._

#### Array (массив, list, индекс)

- **Что это:** Элементы по порядку, у каждого номер-индекс с нуля.
- **Быстро:** Доступ по индексу — O(1); добавление в конец — дёшево.
- **Медленно:** Поиск по значению — O(n); вставка и удаление в середине — O(n).
- **Пример:** Лента постов, которую читают по порядку и дополняют в конец.
- **Когда брать:** Читаешь по позиции и в основном добавляешь в конец.
- **Связи:** Его слабость — поиск по значению — закрывает **Hash Map**; **Stack** и **Queue** часто строятся поверх него.

### Linear search — перебор по значению

> Шкафчик 500 открываешь мгновенно. Но если знаешь только, что лежит внутри, а не номер, — придётся открывать один за другим, пока не найдёшь.

Подвох массива: он быстр, только когда знаешь _индекс_. Чтобы найти элемент по _содержимому_ — «есть ли этот email в списке?» — нужно проверить каждый по очереди. Это **линейный поиск (linear search)**, **O(n)**: на больших списках — медленно. Ровно эту дыру закрывает следующая структура.

_Diagram: Без индекса — проверяем по одному: в худшем случае весь список._

#### Linear search (линейный поиск, перебор)

- **Что это:** Проверить элементы по одному, пока не найдёшь нужный.
- **Цена:** O(n): в десять раз больше данных — в десять раз дольше.
- **Пример:** `emails.includes(x)` на списке из миллиона адресов.
- **Подвох:** Внутри другого цикла превращается в O(n²) — тот самый «тормоз в проде».
- **Связи:** Заменяется поиском в **Hash Map** или **Set** за O(1).

> **Вопрос массива:** «Я обращаюсь к данным по позиции и в основном добавляю в конец — где массив блистает — или ищу по значению и вставляю в середину, где он медленный?»

> Массив — упорядоченная последовательность с индексами: мгновенный доступ по позиции, но O(n) на поиск по значению и вставку в середину.

## 4. Hash Map и Set

Если какая-то структура заслуживает быть твоей рабочей лошадкой по умолчанию — это хеш-таблица. Она закрывает главную слабость массива — поиск по значению — и делает это почти мгновенно.

### Hash Map — пары ключ-значение

> Телефонная книга: ищешь человека по имени и сразу получаешь номер. Ты не листаешь все записи — имя ведёт прямо к ответу.

**Хеш-таблица (hash map; ещё dictionary, hash table или просто map)** хранит данные как **пары ключ-значение (key-value)**: даёшь ключ — получаешь значение. Пользователь по ID, настройка по имени, счётчик по слову — напрямую, по ключу. Массив заставляет знать позицию; хеш-таблица даёт искать по осмысленному имени.

_Diagram: Ключ ведёт прямо к значению — без просмотра остальных записей._

#### Hash Map (хеш-таблица, dictionary, map)

- **Что это:** Пары ключ → значение с поиском по ключу.
- **Быстро:** Поиск, добавление и удаление по ключу — фактически O(1).
- **Медленно:** Порядка нет; найти «по значению», а не по ключу — снова перебор.
- **Пример:** `users[id]`, `settings["theme"]`, подсчёт слов `counts[word] += 1`.
- **Когда брать:** Постоянно ищешь что-то по идентификатору.
- **Связи:** Скорость даёт **Hash function**; без значений превращается в **Set**.

### Hash function — почему поиск мгновенный

> Волшебный шкаф: по метке сразу открывается нужный ящик, другие он не проверяет. Сколько ящиков — неважно.

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

_Diagram: Хеш-функция превращает ключ в номер ячейки — таблица идёт прямо туда._

#### Hash function (хеш-функция)

- **Что это:** Функция, которая по ключу вычисляет место значения в таблице.
- **Как работает:** Один и тот же ключ всегда даёт одно и то же место — поэтому поиск не перебирает записи.
- **Пример:** `hash("eve")` → ячейка 3 → там лежит номер Евы.
- **Связи:** Сердце **Hash Map** и **Set**.

### Set — есть или нет, без значений

> Список гостей на входе: детали не нужны, только «да или нет» — есть это имя в списке? Проверено мгновенно, без листания.

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

_Diagram: Set отвечает «есть или нет» за O(1) и не хранит дубликатов._

#### Set (множество)

- **Что это:** Набор уникальных ключей без значений.
- **Быстро:** Проверка «есть ли?» и добавление — O(1); дубликаты отбрасываются сами.
- **Пример:** `seen = set()` — пропускать письма, которые уже отправили; убрать повторы из списка.
- **Когда брать:** Уникальность и быстрые проверки присутствия.
- **Связи:** Это **Hash Map** без значений.

> **Вопрос таблицы:** «Я ищу по осмысленному ключу или проверяю, есть ли что-то, — то есть делаю ровно то, что хеш-таблица и множество делают мгновенно, а не перебором списка?»

> Хеш-таблица находит значение по ключу фактически за O(1) — рабочая лошадка для поиска по идентификатору. Её родственник Set так же мгновенно отвечает «это здесь есть?».

## 5. Stack и Queue

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

### Stack — последним пришёл, первым ушёл (LIFO)

> Стопка тарелок: кладёшь сверху и берёшь сверху. Последняя положенная — первая, которую возьмёшь.

**Стек (stack)** работает по правилу **LIFO — last in, first out** (последним пришёл — первым ушёл). Добавляешь (**push**) и убираешь (**pop**) с одного конца, поэтому первым выходит самый свежий элемент. Это подходит всему, что вкладывается или разматывается в обратном порядке: история отмены (undo), кнопка «назад», стек вызовов программы (call stack). Обе операции — **O(1)**.

_Diagram: Push кладёт наверх, pop снимает сверху: самый свежий выходит первым._

#### Stack (стек, LIFO)

- **Что это:** Добавляем и убираем только с вершины.
- **Быстро:** `push` и `pop` — O(1).
- **Пример:** Undo в редакторе, кнопка «назад» в браузере, call stack.
- **Когда брать:** Нужен порядок «самое свежее первым» или «отмени последнее».
- **Связи:** Зеркало **Queue**: те же данные, другой конец для выдачи.

### Queue — первым пришёл, первым ушёл (FIFO)

> Очередь в кассу: обслуживают в порядке прихода, новые встают в хвост, следующим идёт тот, кто впереди.

**Очередь (queue)** работает по правилу **FIFO — first in, first out** (первым пришёл — первым ушёл). Добавляешь в хвост (**enqueue**), забираешь спереди (**dequeue**), поэтому элементы обрабатываются в порядке прихода. Это структура для честности и порядка: задачи на обработку, ждущие работы, запросы по очереди — та же идея, что у очереди сообщений из курса про очереди. Как и у стека, операции — **O(1)**.

_Diagram: Новые встают в хвост, обслуживают спереди — в порядке прихода._

#### Queue (очередь, FIFO)

- **Что это:** Добавляем в хвост, забираем с головы.
- **Быстро:** `enqueue` и `dequeue` — O(1).
- **Пример:** Задачи для фоновых воркеров, запросы, которые обслуживают по очереди.
- **Когда брать:** Порядок прихода должен стать порядком обработки.
- **Связи:** Зеркало **Stack**; в большом масштабе вырастает в message queue.

### Правило определяет поведение

> Одна и та же куча работы, две двери: одна отдаёт самое свежее, другая — самое старое. Один выбор — с какого конца брать — меняет всё дальше.

Стек и очередь хранят одно и то же; вся разница — _с какого конца забираешь_. Выбирать между ними — значит выбирать порядок, в котором работа к тебе возвращается: обратный и вложенный (стек) или честный и последовательный (очередь). Маленькое решение с большим эффектом: угадай порядок — и остальная логика встанет на место.

_Diagram: Положили 1, 2, 3: стек отдаст 3, 2, 1, очередь — 1, 2, 3._

> **Вопрос порядка:** «Первым должен выходить самый свежий элемент (стек — для отмены и вложенности) или самый старый (очередь — для честной обработки по порядку)?»

> Stack — последним пришёл, первым ушёл: отмена, вложенность, разворот. Queue — первым пришёл, первым ушёл: честная обработка по порядку. Данные те же; конец, с которого забираешь, — вся разница.

## 6. Tree и Graph

Две последние структуры — для данных, которые не лежат в одну линию, а имеют форму: ветвятся в иерархию или сплетаются в сеть. Так моделируют связи между вещами.

### Tree — иерархия

> Семейное древо или оргструктура компании: одно наверху, дальше ветвится вниз на детей, у тех свои дети. Расходится веером и никогда не замыкается обратно.

**Дерево (tree)** хранит данные как иерархию: сверху **корень (root)**, от него ветвятся **узлы (nodes)** с детьми, и так вниз. Оно моделирует всё вложенное — папки в папках, комментарии и ответы на них, меню категорий. Форма дерева повторяет реальную вложенность, поэтому оно естественный выбор, когда данные — «вещи внутри вещей». Большинство иерархий в софте — деревья под капотом.

_Diagram: Файловая система — дерево: корень, папки-узлы, файлы-листья, без петель._

#### Tree (дерево; root, node)

- **Что это:** Иерархия: у каждого узла есть дети, но нет петель назад.
- **Пример:** Папки и файлы, ветка комментариев, дерево категорий в магазине.
- **Когда брать:** Данные устроены как «вещи внутри вещей».
- **Подвох:** Если впихнуть иерархию в плоский список, придётся склеивать её обратно руками.
- **Связи:** Упорядоченное и ровное дерево — **Balanced tree**; дерево — частный случай **Graph**.

### Balanced tree — поиск за O(log n)

> Ищешь имя в телефонной книге: открываешь середину, потом середину нужной половины, и снова. Каждый шаг выкидывает половину оставшегося.

Хорошо организованное, **сбалансированное (balanced)** дерево даёт мощное свойство: в нём можно искать за **O(log n)**, каждый раз деля пространство пополам — как ищешь слово в словаре, не читая каждую страницу. Логарифм почти не растёт, даже когда данные взрываются: **миллиард элементов — всего около тридцати шагов**. Так базы данных держат поиск быстрым на огромном масштабе: упорядоченные данные в форме дерева, поиск делением пополам.

_Diagram: Ищем 62: больше 50 — направо, меньше 75 — налево. Каждый шаг отбрасывает половину._

#### Balanced tree (сбалансированное дерево поиска)

- **Что это:** Упорядоченное дерево одинаковой глубины со всех сторон.
- **Как работает:** На каждом узле сравниваем и уходим в одну половину — вторую больше не смотрим.
- **Быстро:** Поиск — O(log n): миллиард элементов ≈ 30 шагов.
- **Пример:** Индексы в базах данных: упорядоченные ключи в форме дерева.
- **Связи:** Частный случай **Tree**; в отличие от **Hash Map** хранит порядок.

### Graph — сеть связей

> Карта городов, соединённых дорогами, или люди, связанные дружбой: всё связано со всем в любом узоре, без верха и низа.

**Граф (graph)** — самая общая форма: **узлы (nodes)**, соединённые **рёбрами (edges)**, в любом узоре, включая петли. Он моделирует сети — социальные связи, дороги между городами, ссылки между страницами, зависимости между задачами. Если данные по сути «вещи, связанные с другими вещами», а не иерархия и не линия, — это граф. Многие сложные задачи — кратчайший маршрут, кто с кем связан — в основе графовые.

_Diagram: Узлы и рёбра в любом узоре; петли разрешены — в отличие от дерева._

#### Graph (граф; node, edge)

- **Что это:** Узлы и рёбра между ними — без иерархии, петли разрешены.
- **Пример:** Друзья в соцсети, дороги между городами, ссылки между страницами, зависимости задач.
- **Типичные задачи:** Кратчайший маршрут; кто с кем связан.
- **Когда брать:** Данные — сеть, а не линия и не иерархия.
- **Связи:** **Tree** — это граф без петель с одним корнем.

> **Вопрос формы:** «Эти данные вложены в иерархию (дерево) или связаны в сеть (граф) — и я моделирую эту форму или впихиваю её в плоский список?»

> Tree моделирует иерархию и, если сбалансировано, ищет за O(log n) делением пополам. Graph моделирует сеть связей. Бери их, когда у данных есть форма — вложенная или связанная.

## 7. Как выбирать

С нуля эти структуры почти никто не пишет — они уже есть в твоём языке. Навык — выбрать правильную под задачу и знать Big-O настолько, чтобы почуять плохой выбор до того, как он укусит.

### Dominant operation — выбирай по частой операции

> Кухню собирают под то, что готовят каждый вечер, а не под то, что эффектно смотрится.

Практическое решение почти всегда одно: какую операцию я делаю чаще всего, и какая структура делает _именно её_ быстрой? Постоянный поиск по ключу — **Hash Map**. Порядок прихода — **Queue**. В основном чтение по позиции — **Array**. Пусть **доминирующая операция (dominant operation)** выбирает структуру, а с медленностью в редких операциях смирись. Оптимизируй частый случай — структура и есть способ.

_Diagram: Назови свою частую операцию — она сама укажет на структуру._

#### Dominant operation (выбор по частой операции)

- **Идея:** Структуру выбирает самая частая операция, а не привычка.
- **Пример:** Тысячи поисков пользователя по ID в секунду → **Hash Map**, даже если порядок теряется.
- **Цена:** Редкие операции станут медленнее — это осознанный размен.
- **Связи:** Применение **Trade-off** на практике.

### Map before loop — сначала таблица, потом цикл

> Прежде чем искать человека в толпе по лицам, проверь, нет ли списка гостей: список отвечает мгновенно на то, что поиск делает медленно.

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

_Diagram: Было: цикл в цикле, миллион проверок. Стало: один раз строим таблицу, дальше O(1) на каждый поиск._

#### Map before loop (таблица вместо вложенного цикла)

- **Проблема:** Для каждого элемента перебираем другой список — O(n²), «тормоз в проде».
- **Идея:** Один раз построить **Hash Map** или **Set**, дальше искать в нём за O(1).
- **Пример:** Вместо `users.find(u => u.id === order.userId)` в цикле по заказам — заранее `byId` и `byId[order.userId]`.
- **Цена:** Немного памяти под таблицу.
- **Связи:** Превращает **Linear search** внутри цикла в O(1).

#### Прежде чем выбрать структуру

- **Какая операция главная** — поиск, порядок, добавление/удаление?
- **Поиск по ключу?** Hash Map (или Set для «есть ли») — O(1).
- **Доступ по позиции и добавление в конец?** Подходит Array.
- **Важен порядок выдачи** — самое свежее (Stack) или самое старое (Queue)?
- **Вложенные или связанные данные** — Tree или Graph?
- **Какой Big-O на большом n** — и нет ли где-то скрытого O(n²)?

#### Признаки, что ты выбираешь хорошо

- Выбираешь структуру по **частой операции**, а не по привычке.
- Берёшь **Hash Map или Set** вместо перебора списка, чтобы найти или убрать дубликаты.
- Можешь назвать **Big-O** своего горячего пути — и в нём нет скрытого **O(n²)**.
- Берёшь **Stack или Queue**, когда важен порядок выдачи, и **Tree или Graph**, когда у данных есть форма.
- Код остаётся быстрым, когда данные растут, — потому что ты выбрал **форму** раньше, чем масштаб её вскрыл.

### Как всё связано

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

Big-O — линейка, которой меряют все структуры. Hash Map закрывает слабость Array (поиск по значению), Set — это Hash Map без значений. Stack и Queue — последовательность с правилом «забирай только с конца». Tree даёт иерархию, а сбалансированное — поиск за O(log n); Graph снимает последнее ограничение и разрешает любые связи.

_Diagram: Big-O меряет всех; каждая структура отвечает на слабость или ограничение соседней._

## Шпаргалка: все 16 понятий

### Основы

- **Data Structure** (структура данных): Способ расположить данные так, чтобы частые операции были быстрыми.
- **Trade-off** (размен): Сила в одной операции стоит слабости в другой.

### Big-O

- **Big-O notation** («О большое»): Как растёт работа, когда растут данные n.
- **Complexity classes** (O(1), O(log n), O(n), O(n²)): Константа, логарифм, линейная, квадратичная. O(n²) — тревога.

### Массив

- **Array** (массив, list): По порядку, с индексом: по позиции O(1), вставка в середину O(n).
- **Linear search** (перебор): Ищем по значению, проверяя по одному. O(n).

### Хеш-таблица

- **Hash Map** (dictionary, map): Ключ → значение, поиск по ключу фактически O(1). Без порядка.
- **Hash function** (хеш-функция): Вычисляет по ключу, где лежит значение, — поэтому без перебора.
- **Set** (множество): Только ключи: «есть ли?» за O(1), без дубликатов.

### Порядок

- **Stack** (LIFO): Последним пришёл — первым ушёл. Undo, «назад», call stack.
- **Queue** (FIFO): Первым пришёл — первым ушёл. Обработка в порядке прихода.

### Форма

- **Tree** (дерево): Иерархия: корень, узлы, дети, без петель.
- **Balanced tree** (сбалансированное дерево): Поиск делением пополам — O(log n). Так работают индексы баз.
- **Graph** (граф): Узлы и рёбра в любом узоре. Сети, маршруты, зависимости.

### Как выбирать

- **Dominant operation** (частая операция): Структуру выбирает самая частая операция.
- **Map before loop** (таблица вместо цикла): Перед вложенным перебором — построй Hash Map или Set.

> Ты не строишь их с нуля — ты их выбираешь. Подбирай структуру под частую операцию, тянись к таблице раньше, чем к циклу, и пусть Big-O предупредит тебя раньше, чем масштаб.

Конец экспресс-курса · 7 глав · 16 понятий

Дальше — практика: найди в своём коде место, где ты идёшь циклом по списку, чтобы найти или сопоставить что-то, и замени его поиском по хеш-таблице или множеству — потом посмотри, насколько это быстрее на больших данных. Потом для одной медленной операции выведи её Big-O и спроси, меняет ли другая структура форму. Но держи главную мысль: правильная форма делает сложное простым. Большинство ответов на «почему медленно?» — «оно лежит не в той структуре», а выбрать правильную — самая дешёвая скорость, которую ты когда-либо купишь.