Структура данных — это способ организации и хранения данных, который позволяет эффективно выполнять операции над ними: добавление, удаление, поиск, изменение, сортировку и т. д. Правильный выбор структуры данных критически влияет на производительность программы.
Классификация структур данных
- По способу организации:
- линейные — элементы расположены последовательно (массивы, списки, стеки, очереди);
- нелинейные — элементы связаны иерархически или произвольно (деревья, графы).
- По изменчивости размера:
- статические — размер фиксирован при создании (обычные массивы);
- динамические — размер может меняться во время работы программы (динамические массивы, списки).
- По связности элементов:
- несвязные — элементы хранятся в смежных ячейках памяти (массивы);
- связные — элементы содержат ссылки на другие элементы (связные списки, деревья).
- По доступности элементов:
- с прямым доступом (массивы — доступ по индексу);
- с последовательным доступом (связные списки — нужно пройти предыдущие элементы).
Основные структуры данных и их характеристики
- Массив (Array)
- Описание: набор элементов одного типа, расположенных в памяти последовательно. Каждый элемент имеет индекс (обычно начинается с 0).
- Виды: одномерные, многомерные (матрицы, тензоры).
- Операции: быстрый доступ по индексу O(1), медленная вставка/удаление в середине O(n).
- Применение: хранение упорядоченных данных фиксированного размера, матрицы, таблицы.
- Динамический массив (Dynamic Array)
- Описание: массив с автоматически изменяемым размером. При заполнении выделяется новый, больший блок памяти.
- Операции: доступ по индексу O(1), амортизированная вставка в конец O(1), вставка в середину O(n).
- Применение: списки элементов переменного размера, реализация других структур.
- Связный список (Linked List)
- Описание: последовательность узлов, каждый из которых содержит данные и ссылку на следующий узел (односвязный) или на предыдущий и следующий (двусвязный).
- Виды: односвязный, двусвязный, кольцевой.
- Операции: быстрая вставка/удаление O(1) при наличии указателя на узел, медленный доступ по индексу O(n).
- Применение: очереди, стеки, реализация хэш‑таблиц.
- Стек (Stack)
- Принцип: LIFO (Last In, First Out — «последним пришёл — первым ушёл»).
- Операции:
push(добавить в вершину),pop(удалить из вершины),peek(просмотреть вершину). - Реализация: на массивах или связных списках.
- Применение: рекурсия, синтаксический анализ, отмена действий (undo).
- Очередь (Queue)
- Принцип: FIFO (First In, First Out — «первым пришёл — первым ушёл»).
- Операции:
enqueue(добавить в конец),dequeue(удалить из начала),peek. - Виды: обычная, с приоритетом (Priority Queue).
- Применение: буферы, планирование задач, алгоритмы обхода (BFS).
- Дерево (Tree)
- Описание: иерархическая структура из узлов, где каждый узел имеет родителя (кроме корня) и может иметь потомков.
- Виды: бинарное дерево, двоичное дерево поиска (BST), AVL‑дерево, красно‑чёрное дерево, B‑дерево.
- Операции: поиск, вставка, удаление — обычно O(logn) для сбалансированных деревьев.
- Применение: файловые системы, индексы баз данных, синтаксические деревья.
- Граф (Graph)
- Описание: множество вершин (узлов), соединённых рёбрами. Рёбра могут быть направленными или ненаправленными, взвешенными или невзвешенными.
- Способы представления: матрица смежности, список смежности.
- Операции: обход (DFS, BFS), поиск пути, топологическая сортировка.
- Применение: социальные сети, карты дорог, сетевые модели.
- Хэш‑таблица (Hash Table)
- Описание: структура, использующая хэш‑функцию для преобразования ключа в индекс массива.
- Операции: добавление, поиск, удаление — в среднем O(1).
- Проблемы: коллизии (решаются методами цепочек или открытой адресации).
- Применение: словари, кэши, базы данных.
- Множество (Set)
- Описание: коллекция уникальных элементов без определённого порядка.
- Реализация: на основе хэш‑таблиц или деревьев.
- Операции: добавление, удаление, проверка принадлежности, объединение, пересечение.
- Применение: фильтрация дубликатов, математические операции над множествами.
- Префиксное дерево (Trie)
- Описание: дерево, где каждый узел представляет префикс строки. Используется для хранения строк с общими началами.
- Операции: быстрый поиск по префиксу, добавление, удаление.
- Применение: автозаполнение, проверка орфографии, маршрутизация IP.
Критерии выбора структуры данных
При выборе структуры данных учитывают:
- тип операций: какие операции будут выполняться чаще всего (поиск, вставка, обход);
- объём данных: для больших объёмов критична асимптотическая сложность;
- частота изменений: как часто добавляются/удаляются элементы;
- потребность в упорядоченности: нужны ли отсортированные данные;
- ограничения по памяти: некоторые структуры требуют больше памяти на служебную информацию (указатели, хэш‑таблицы);
- сложность реализации: простые структуры легче отлаживать.
Типичные ошибки при выборе
- использование массива при частых вставках/удалениях в середине;
- применение линейного поиска в неупорядоченных структурах вместо хэш‑таблиц;
- игнорирование балансировки деревьев, ведущее к деградации производительности;
- выбор структуры с высокой сложностью памяти для ограниченных ресурсов.
Вывод: знание основных структур данных и их характеристик позволяет выбирать оптимальные решения для конкретных задач. Это напрямую влияет на скорость работы программы, потребление памяти и удобство сопровождения кода.