Что такое структуры данных: 8 видов, классификация и выбор по задаче

Что такое структура данных

Структура данных в информатике — способ хранения и организации данных с чёткими правилами доступа к ним. Всё начинается с простого объявления переменной: даже одно число уже лежит в определённой ячейке памяти по конкретному адресу.

Алгоритм и структура данных неразделимы. Алгоритм описывает порядок шагов; структура задаёт, где и как хранятся данные, с которыми он работает. Вирт объединил это в одну формулу, и с тех пор обе темы изучают вместе. Линейные структуры выстраивают элементы в последовательную цепочку; нелинейные организуют разветвлённые сети и иерархии.

Линейные структуры данных

В линейных структурах элементы образуют последовательность — обход идёт по одному пути, от первого элемента к последнему. К этому классу относятся четыре вида: массив, стек, очередь и связный список. Каждый из них решает свой сценарий и имеет собственные правила доступа к элементам.

Массив — базовая линейная структура

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

Стек и очередь: принципы LIFO и FIFO

Стек работает по принципу LIFO — последний добавленный элемент извлекается первым. Основные операции: Push (добавить в стек), Pop (извлечь), Top (посмотреть вершину), isEmpty (проверить на пустоту). Применение: функция отмены (Undo) в редакторах, кнопка «Назад» в браузере Chrome.

Очередь — FIFO: первый добавленный уходит первым. Операции: Enqueue (добавить в конец), Dequeue (извлечь из начала). Применение: планировщик задач операционной системы, доставка сообщений. Двусторонняя очередь (дек) позволяет добавлять и извлекать элементы с обоих концов.

Связный список — гибкость против массива

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

Нелинейные структуры данных

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

Граф — сеть вершин и рёбер

Граф — множество вершин, соединённых рёбрами, без ограничений на порядок связей. Два подтипа: ориентированный граф (направление ребра важно) и неориентированный (связь равнозначна в обе стороны).

Граф хранят двумя способами: матрица смежности (таблица N×N — единица, если ребро есть, ноль, если нет) и список смежности (для каждой вершины — список её соседей). Поиск в ширину (BFS) обходит граф по уровням и находит кратчайший маршрут — именно так работает Google Maps. Поиск в глубину (DFS) уходит вглубь перед возвратом и применяется при поиске пути в лабиринтах. Дерево — частный случай графа: ациклический связный граф с единственным корнем.

Дерево — иерархия данных

Дерево — иерархическая структура без циклов с единственным корнем. Каждый узел имеет ровно одного родителя, кроме корневого. Подтипы: бинарное дерево (не более двух потомков у узла), дерево двоичного поиска (BST: левый узел < корень < правый), самобалансирующееся дерево AVL. Три обхода: прямой (сверху вниз), симметричный (слева направо), обратный (снизу вверх).

Префиксное дерево (Trie) специализируется на строках: каждый узел хранит один символ, путь от корня до листа образует слово. Применяется в автодополнении поисковых запросов, словарях Т9 и системах проверки орфографии.

Хэш-таблица — доступ за O(1)

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

Как выбрать структуру данных под задачу

Структура данных в программировании выбирается под конкретный сценарий — универсального варианта не существует.

Быстрый доступ по индексу → массив. Отмена последних действий, история браузера → стек. Планировщик задач, очередь сообщений → очередь. Частые вставки и удаления в середину → связный список. Мгновенный поиск по ключу → хэш-таблица. Иерархические данные, файловая система, организационная структура → дерево. Сеть связей между объектами, маршруты, социальный граф → граф. Знание этих сценариев — базовый навык при проектировании информационных систем и системном анализе данных.

Хотите разобраться в устройстве IT-систем на практике? В рамках федерального проекта «Активные меры содействия занятости» доступны программы «Специалист по информационным системам: от организации до сопровождения ИТ-проектов» и «Системный аналитик: с нуля до проектирования систем» — онлайн, без отрыва от работы. Смотрите каталог доступных программ.

Часто задаваемые вопросы

Какие бывают структуры данных в программировании?

Выделяют 8 базовых: массив, стек, очередь, связный список, граф, дерево, префиксное дерево и хэш-таблица. По принципу обхода делятся на линейные — массив, стек, очередь, список — и нелинейные — граф, дерево, хэш-таблица.

Чем отличаются линейные и нелинейные структуры данных?

В линейных элементы выстроены в последовательность — обход идёт по одному пути. В нелинейных обход многовариантен, данные не следуют строго друг за другом. Линейные: массив, стек, очередь, список. Нелинейные: граф, дерево.

В чём разница между стеком и очередью?

Стек — LIFO: последний добавленный элемент извлекается первым (применение: Undo, история браузера). Очередь — FIFO: первый добавленный уходит первым (применение: планировщик задач ОС). Ключевое отличие — принцип доступа к элементам.

Что такое коллизия в хэш-таблице и как с ней бороться?

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

К какому типу структур относятся графы и деревья?

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

Что такое BFS и DFS?

Поиск в ширину (BFS) — обход графа по уровням: сначала все соседи узла, затем их соседи. Используется в навигационных сервисах для нахождения кратчайшего маршрута. Поиск в глубину (DFS) уходит вглубь перед возвратом и применяется при поиске пути в лабиринтах.

Когда использовать связный список вместо массива?

Связный список предпочтителен при частых вставках и удалениях в середину — сдвигать остальные элементы не нужно. Массив эффективнее для быстрого доступа по индексу O(1). Ключевое различие: массив хранит элементы в смежных ячейках памяти, список соединяет их указателями.

Почему алгоритмы и структуры данных изучают вместе?

Никлаус Вирт в 1976 году сформулировал: «Алгоритмы + структуры данных = программы». Эффективность алгоритма напрямую зависит от выбранной структуры — сортировка на массиве и на связном списке принципиально различаются. Структура задаёт правила хранения, алгоритм по ним работает.