Почти любая программа что-то хранит и что-то с этим делает: список товаров в корзине, сообщения в чате, точки на карте. Вопрос, который встаёт всегда, — как разложить эти данные, чтобы с ними было удобно и быстро работать. От ответа зависит, будет ли поиск нужной записи мгновенным или программа задумается на секунды, влезет ли всё в память и легко ли добавить новый элемент. Ответ на этот вопрос и дают структуры данных и алгоритмы. Этот раздел — маршрут по ним с нуля, от массива до графа.
Что такое структура данных и алгоритм
Структура данных — это способ организации данных в памяти (или на диске). Массив, связанный список, стек, дерево, хеш-таблица — всё это разные способы разложить одни и те же данные. Каждый способ по-своему хорош: один быстро ищет, другой быстро вставляет, третий экономит память.
Алгоритм — это последовательность шагов, решающая задачу над данными. Для большинства структур базовые задачи одни и те же:
- вставить новый элемент;
- найти нужный элемент;
- удалить элемент;
- перебрать все элементы по очереди;
- отсортировать элементы по порядку.
Структура и алгоритм связаны: способ хранения определяет, какие операции будут дешёвыми, а какие — дорогими. Поэтому их изучают вместе.
Три роли структур данных
Где это вообще пригодится? Условно — три большие области.
Хранение реальных данных. Данные о людях, товарах, заказах, операциях. Классическая аналогия — картотека с карточками: каждая карточка описывает одну сущность (человека, товар), а вся стопка — базу. Как только карточек становится много, возникают те самые вопросы: как быстро найти нужную, как добавить новую, как отсортировать по алфавиту. Реальные базы данных сложнее картотеки, но идея та же.
Инструментарий программиста. Не все структуры видит пользователь. Многие нужны самой программе как рабочий инструмент: стек, чтобы разобрать выражение или откатить действие; очередь, чтобы обработать задачи по порядку; приоритетная очередь, чтобы всегда доставать самое срочное. Это вспомогательные структуры «под капотом».
Моделирование. Некоторые структуры прямо отражают реальный мир. Граф моделирует маршруты между городами, связи в социальной сети или зависимости между задачами. Очередь моделирует клиентов в банке или машины на въезде. Здесь структура — это карта самой задачи.
Базовые термины
Несколько слов, которые встречаются постоянно; проще договориться о них сразу.
- Запись (record) — логический блок, описывающий одну сущность целиком: одного человека, один товар, один заказ. В картотеке это одна карточка, а в коде — обычно объект класса.
- Поле (field) — отдельная часть записи: имя, адрес, телефон. В объекте это его переменная.
- Ключ (key) — поле, по которому ищут запись. Например, ищем сотрудника по фамилии — фамилия здесь ключ. У одних и тех же данных ключей может быть несколько: сегодня ищем по фамилии, завтра — по телефону.
Эти термины помогают говорить об операциях единообразно: «найти запись по ключу», «вставить запись», «удалить по ключу» — независимо от того, какая структура внутри.
Обзор: какая структура для чего
Главная мысль всего раздела: идеальной структуры нет — у каждой свои сильные и слабые стороны. Выбор всегда компромисс. Вот карта с высоты птичьего полёта; сейчас термины могут быть незнакомы — к каждому вернёмся в своей статье.
| Структура | Сильна в | Слаба в |
|---|---|---|
| Массив | доступ по индексу, вставка в конец | поиск, удаление, фиксированный размер |
| Упорядоченный массив | поиск (двоичный) | вставка и удаление |
| Стек | доступ по принципу «последним пришёл — первым вышел» | доступ к остальным элементам |
| Очередь | доступ по принципу «первым пришёл — первым вышел» | доступ к остальным элементам |
| Связанный список | вставка и удаление | поиск |
| Двоичное дерево поиска | быстрые поиск, вставка, удаление (если сбалансировано) | сложное удаление, деградация без баланса |
| Сбалансированное дерево (красно-чёрное, 2-3-4) | всё быстро и гарантированно | сложность реализации |
| Хеш-таблица | очень быстрый доступ по ключу | нет порядка, память, плохо без ключа |
| Куча (пирамида) | быстро достать наибольший/наименьший | доступ к остальным элементам |
| Граф | моделирование связей | некоторые алгоритмы дороги |
Не пытайтесь запомнить таблицу — она станет очевидной по мере чтения. Пока достаточно уловить принцип: у массива быстрый доступ, но медленный поиск; у хеш-таблицы молниеносный доступ по ключу, но нет порядка; у дерева всё сбалансировано, но сложнее внутри.
Как измеряют «быстро» и «медленно»
Слова «быстро» и «медленно» скоро станут точными. Скорость алгоритма измеряют не в секундах (они зависят от железа), а в том, как растёт число операций с ростом объёма данных — это называют O-нотацией. Поиск в массиве перебором на миллионе элементов делает до миллиона шагов; двоичный поиск в упорядоченном массиве — около двадцати. Эту разницу и описывает O-нотация; подробно разберём её в статье про массивы и двоичный поиск.
Коротко
- Структура данных — способ организации данных; алгоритм — шаги операций над ними (вставка, поиск, удаление, перебор, сортировка).
- Структуры нужны для трёх вещей: хранить реальные данные, служить инструментом программисту, моделировать задачи из мира.
- Базовый словарь — запись, поле, ключ — позволяет говорить об операциях единообразно.
- Идеальной структуры нет: каждая быстра в одном и медленна в другом, выбор — всегда компромисс под задачу.
- «Быстро» измеряют O-нотацией — тем, как растёт число операций с объёмом данных.
Дальше — по порядку: массивы, двоичный поиск и O-нотация, затем простая сортировка и остальные структуры. Каждая статья самодостаточна, но идут они от простого к сложному, поэтому читать удобнее по очереди.