Зачем компьютеру «полочки для данных»
Представь библиотеку без каталога: чтобы найти книгу, придётся перебрать все полки. Структуры данных — это и есть каталоги, полки и ящички внутри компьютерной памяти. Правильный выбор структуры ускоряет программу в тысячи раз; неправильный — превращает секундную задачу в часовую.
Формально структура данных — способ хранения элементов в памяти вместе с набором операций (добавление, удаление, поиск, обход). Одни и те же числа можно хранить в массиве, списке, дереве или хеш-таблице — и каждый вариант ускоряет одни операции за счёт других.
Линейные структуры: массивы, списки, стеки
Массив (array) — элементы лежат подряд в памяти, доступ по индексу за O(1). Обратная сторона: вставка в середину стоит O(n), потому что нужно сдвигать все последующие ячейки. Массивы появились ещё в FORTRAN (1957) и остаются самой используемой структурой.
Связный список (linked list) — каждый элемент хранит указатель на следующий. Вставка и удаление за O(1) в любом месте, но поиск по номеру — O(n). Алгоритм Аллена Ньюэлла и Герберта Саймона (1955–1956) использовал списки в Logic Theorist — первой программе искусственного интеллекта.
Стек (stack) — «магазин»: последний пришёл — первый ушёл (LIFO). Калькулятор HP-35 (1972) работал именно на стеке. Очередь (queue) — первый пришёл — первый ушёл (FIFO), как очередь в магазине.
Деревья: от двоичных до B-деревьев
Двоичное дерево поиска (BST) — каждый узел хранит значение, левое поддерево содержит значения меньше, правое — больше. Поиск, вставка и удаление занимают O(log n) в среднем, но O(n) в худшем случае, когда дерево вырождается в список.
Решение придумали Г.М. Адельсон-Вельский и Е.М. Ландис в 1962 году — AVL-дерево, первая самобалансирующаяся структура. Она гарантирует O(log n) для всех операций за счёт поворотов при вставке. Позднее появились красно-чёрные деревья Р. Байера (1972), которые используются в ядре Linux и стандартной библиотеке C++ (std::map).
B-дерево (Байер и Маккрейт, 1970) — дерево с сотнями ключей в узле. Оптимизировано для дисковых операций: один узел = одна страница диска. Все современные базы данных (PostgreSQL, MySQL) используют B-деревья или их вариант B+-дерево для индексов.
Хеш-таблицы: поиск за O(1)
Хеш-функция превращает ключ (строку, число) в индекс массива. В идеале поиск занимает O(1) — одно обращение к памяти. Хеширование предложил Ханс Петер Лун (IBM, 1953), а первая крупная реализация появилась в компиляторе Lisp Джона Маккарти (1958).
Проблема — коллизии: два ключа попадают в одну ячейку. Два подхода: цепочки (в каждой ячейке — список) и открытая адресация (ищем следующую свободную ячейку). Python dict, Java HashMap, JavaScript Object — все используют хеш-таблицы под капотом.
Графы: структура для связей
Граф — множество вершин и рёбер между ними. Хранится либо как матрица смежности (массив N×N), либо как список смежности (для каждой вершины — список соседей). Матрица быстро проверяет наличие ребра, но занимает O(N²) памяти. Список экономит память для разреженных графов.
Социальные сети (Facebook — 3 млрд вершин), маршрутизация GPS (OpenStreetMap — 8 млрд рёбер) и интернет-маршрутизация (BGP) — всё это задачи на графах. Алгоритм Дейкстры (1959) для кратчайших путей и PageRank Google (1998) работают именно с графовыми структурами.
Как выбрать структуру: шпаргалка
Выбор зависит от главной операции. Частый поиск по ключу — хеш-таблица. Сортированные данные с быстрой вставкой — сбалансированное дерево. Очередь задач — heap (куча). Текст с частыми вставками — rope (верёвка). Нет универсального ответа — структура подбирается под задачу, как инструмент под материал.