1. Структуры данных
Структура данных задаёт способ представить и организовать данные так, чтобы поддерживать нужные операции: поиск, добавление, удаление, обход или обновление.
Массив даёт быстрый доступ по индексу, связный список облегчает вставки в известных позициях, а дерево или хеш-таблица предлагают иные компромиссы между временем, памятью и порядком элементов. «Оптимальной» структуры без задачи не существует: выбор зависит от частоты операций, объёма данных и требований к корректности.
1. Структуры данных
Массивы и списки
Статические и динамические структуры, очереди и стеки. Базовые линейные коллекции элементов с последовательным доступом.
Деревья
Деревья — иерархические структуры данных. BST: поиск за O(log n). AVL и красно-чёрные — самобалансирующиеся. B-деревья — основа PostgreSQL и MySQL.
Графы
Граф — математическая модель из вершин и соединяющих их рёбер. Вершины представляют объекты, а рёбра — выбранные отношения между ними: например, станции и маршруты, люди и знакомства или задачи и зависимости. Рёбра могут быть направленными или иметь вес, если важно направление связи либо её стоимость. Графовая модель показывает структуру связей, но сама по себе не объясняет причины этих связей; алгоритмы обхода, маршрутизации и поиска компонент решают уже отдельные задачи над графом.
Хеш-таблицы
Мгновенный доступ по ключу, разрешение коллизий и ассоциативные массивы. Структуры для O(1) поиска.