Структуры данных в программировании: что это и какие бывают

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

Что такое структура данных и для чего она нужна

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

Благодаря структурам данных можно:

• Логически структурировать и группировать информацию, делая код более понятным и легко поддерживаемым.

• Хранить уникальные элементы, избегая дублирования информации (например, через хеш-таблицы).

• Оптимизировать процесс поиска, добавления, удаления и обновления данных.

• Экономно использовать память, например, через битовые и компактные массивы.

• Упростить выявление и устранение ошибок.

Классы структур данных

На практике выделяются основные структуры данных:

1. Примитивная. Обладает фиксированной памятью и представляет простые значения: целые числа, символы и прочее.

2. Сложная. Позволяет хранить множество значений и работает с более сложными операциями: добавление, удаление, поиск, сортировка данных и т. д. Сюда относятся массивы, списки, векторы и другие типы структур.

Среди сложных выделяются:

1. Линейная. Характеризуется сохранением элементов, которые идут один за другим и доступны в определённой последовательности. Примерами линейных структур данных являются массивы, списки, стеки и очереди.

2. Нелинейная. Элементы могут иметь несколько связей, образуя иерархические, сетевые или произвольные структуры. Примерами нелинейных структур являются деревья и графы.

В линейных можно выделить такие подтипы:

1. Статистическая. Имеет фиксированный размер памяти, что ускоряет доступ к выбранным элементам.

2. Полустатистическая. Комбинация статических и динамических элементов, обеспечивающая баланс между эффективностью использования памяти и гибкостью работы с данными.

3. Динамическая. Здесь размер и структура могут меняться динамически. Это делает управление данными более гибким и позволяет проводить операции с конкретными элементами в любой момент.

Основные алгоритмические типы структур данных

Хеш-таблицы

Неупорядоченная коллекция пар «ключ — значение», где каждый ключ уникален. Хеш-таблица используется для реализации структур данных (map, dict, set и т. д.), особенно полезна для хранения, поиска и добавления элементов.

Операции с хеш-таблицами:

• Вставка. Позволяет добавить в хеш-таблицу элемент с определённым ключом. Сначала ключ преобразуется в хеш-значение, затем размещается в соответствующей ячейке таблицы.

• Удаление. Удаляет элемент с заданным ключом из хеш-таблицы. Сначала ключ преобразуется в хеш-значение, после чего проводится сама операция.

• Поиск. Помогает найти элемент в хеш-таблице через уникальный ключ.

В хеш-таблицах можно проводить следующие действия:

• Обновление. Меняет значение существующего в таблице элемента без переиндексации его ключа.

• Подсчёт элементов. Показывает, сколько элементов находится в хеш-таблице.

• Разрешение коллизий. Применяется, когда несколько ключей преобразуются в одно и то же хеш-значение. Ошибки корректируются через операции «Поиск» и «Вставка».

Где применяются хеш-таблицы:

• Реализация словарей и ассоциативных массивов.

• Кеширование данных или вычислений.

• Маркировка посещённых URL.

• Быстрый поиск и индексации данных (контакты, номера телефонов и т. д.) в CPaaS-сервисах вроде Exolve.

• Управление кешем объектов в приложениях и играх.

• Основа во многих базах данных для хранения большего объёма данных.

Массивы

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

Задача массива — организовать удобную сортировку данных или поиск соответствующего набора значений.

Операции с массивами:

• Добавление. Предназначена для вставки нового элемента в конец существующей структуры данных.

• Обновление. Позволяет менять и присваивать новые значения элементам.

• Удаление. Можно сжимать, удаляя элементы.

• Сортировка порядке возрастания или убывания элементов, например, через алгоритмы быстрой или пузырьковой сортировки.

• Копирование элементов.

• Объединение. Для создания новых массивов с элементами из двух или больше исходников.

Где применяются массивы:

• Решение матричных задач.

• Применение алгоритма сортировки.

• Реализация стеков, очередей, хеш-таблиц.

• Планирование работы процессора.

• Создание справочной таблицы в компьютерах.

• Обработка речи, где каждый речевой сигнал представляет собой массив.

• Работа с системами управления баз данных: учёт книг, журналов или статей, учеников и студентов, голосов и решений и т. д.

• Создание компьютерных игр вроде онлайн-шахмат, с сохранением прошлых и текущих ходов игрока для указания позиции фигур.

Связный список

Непримитивная структура, создающая коллекции элементов в последовательном порядке. В этом формате узлы хранятся в несмежных ячейках памяти. Списки бывают односвязными, со ссылкой на следующий объект, и двусвязными — в том числе со ссылкой на предыдущий объект.

Это гибкая структура, где можно взаимодействовать с элементами списка без предварительного выделения фиксированного объёма памяти, как это делается в тех же массивах.

Операции со связанными списками:

• Инициализация. Инициировать список можно через создание головного узла. Каждый новый узел содержит значение и ссылку на следующий фрагмент.

• Вставка. Данные можно добавлять в начало, конец или обозначенную позицию связанного списка.

• Удаление. Делается через обновления ссылки предыдущего узла, чтобы та указывала на следующую ячейку списка.

• Поиск. Поиск нужного элемента начинается с головного узла и распространяется на следующие ячейки до тех пор, пока подходящий элемент не будет найден.

• Обновление. Проводится путём изменения данных, которые находятся в выбранном элементе.

• Обход. По узлам связанного списка можно перемещаться, начиная с головного узла и следуя ссылкам на следующие элементы, вплоть до конца всего списка.

• Обращение списка. Связанный список можно обратить вспять, обновив ссылки каждого узла таким образом, чтобы они указывали на предыдущий, а не на следующий элемент.

Где применяются связные списки:

• Выполнение арифметических операций с длинными целыми числами.

• Представление разреженных матриц.

• Связанное размещение файлов.

• Отображение контейнеров изображений (для просмотра прошлых, текущих и следующих картинок).

• Циклическое планирование для отслеживания ходов в многопользовательских играх.

• Упорядоченная связь песен в плейлисте и т. д.

Стек

Это линейная структура, которая функционирует по принципу LIFO, где последний добавленный элемент будет удаляться или извлекаться первым. К примеру, при открытии нескольких окон в Windows, активным останется именно последнее задействованное окно.

Операции со стеком:

• Добавление. Элемент добавляется на вершину и заменяет прежнее значение.

• Удаление. Выталкивание всех элементов из стека, что приводит к его очистке и восстановлению пустого состояния.

• Чтение головного элемента. Извлечение значения, которое было добавлено последним и находится в верхней части стека.

Также со стеком можно проводить следующие действия:

• Просмотр. С помощью этой операции верхний элемент можно осмотреть, не удаляя его.

• Размер. Позволяет просмотреть количество элементов.

• Поиск. Находит, возвращает на позицию или сообщает об отсутствии конкретного элемента.

• Проверка на пустоту или заполненность. Определяет наличие или отсутствие данных в стеке.

Где применяются стеки:

• Вычисление и преобразование арифметических выражений.

• Управление памятью.

• Обработка вызовов функций.

• Преобразование выражений из инфиксных в постфиксные.

• Воспроизведение следующей или предыдущей песни.

• Отслеживание ранее посещённых сайтов в браузере.

• Формирование журнала вызовов в мобильном приложении.

Очередь

Структура линейного порядка, в отличие от стека, основана на принципе FIFO, где вначале обрабатывается первый сохранённый элемент данных.

Очередь отлично справляется с управлением заданий для ОС, учётом товаров на складе, обработкой сетевых пакетов и т. д.

Операции с очередью:

• Добавление. Элемент можно добавлять в конец до момента обработки.

• Удаление. Позволяет извлечь и обработать элемент из начала очереди.

• Front. Чтение или получение значения, находящегося в начале, без его удаления.

• Rear. Чтение или получение значения элемента, находящегося в конце очереди, без его удаления.

Где применяется очередь:

• Обработка трафика веб-сайта.

• Планирование и учёт запросов к общему ресурсу: распечатка на принтере, планирование задач процессора и т. д.

• Обработка прерывания, планирование заданий, переключение приложений в ОС.

• Асинхронная передача данных.

• Загрузка нескольких фото или видео и т. д.

Дерево

Иерархическая структура данных с разветвлённой системой элементов. Самый верхний узел дерева называется «корневым» — он ведёт к «родительским» узлам, которые делятся на «дочерние». Структура завершается «листами» — конечной точкой без «дочерних» узлов. Все элементы дерева соединены «рёбрами».

Деревья бывают бинарными, красно-чёрными, AVL и т. д. Каждый из видов обладает уникальными свойствами и способом применения. У любого дерева:

• В каждый узел, кроме корневого узла, входит одна ветвь.

• Существует узел, в который не входит ни одна ветвь.

Операции с деревьями:

• Вставка. Позволяет добавить новый узел в соответствии с правилами, присущими конкретному типу дерева. В двоичном поисковом дереве новый узел вставляется с условием сохранения порядка элементов.

• Балансировка. В некоторых типах деревьев (AVL, красно-чёрные) можно проверить, насколько сбалансированы и равномерны «рёбра».

• Обход. Помогает посетить все узлы дерева в определённом порядке. Для этого можно использовать прямой, обратный, симметричный метод обхода.

• Поиск. Находит узел по заданному ключу или значению. Процедура начинается с корня и рекурсивно движется вниз до получения результата.

• Удаление. Удаление узла из дерева и корректировка структуры для поддержания баланса или других свойств.

Где применяются деревья:

• Моделирование и управление поведением персонажей в видеоиграх.

• Добавление индексов в базы данных.

• Структурирование файловой системы.

• Создание и организация иерархии задач и заданий в системах управления проектами.

• Представление синтаксической структуры программного кода в компиляторах и анализаторах.

• Создание иерархических меню и древовидных структур навигации.

Граф

Нелинейная абстрактная структура данных, которая состоит из фиксированного конечного набора узлов или вершин. Соединена рёбрами — линиями, сцепляющими узлы всей структуры.

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

Операции с графами:

• Добавление вершины. Создаёт в графе новую вершину. Операция нужна для формирования нового элемента или сущности в модели.

• Добавление ребра. Связывает две вершины, задаёт направление и при необходимости вес ребра. Операция помогает моделировать отношение между вершинами.

• Удаление вершины. Исключает из графа выбранную вершину и связанные с ней рёбра.

• Удаление ребра. Разрывает соединение между двумя вершинами, отменяя указанное ребро. Полезно, когда связь между вершинами более неактуальна.

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

• Вычисление кратчайших путей между вершинами. Это делается с помощью алгоритмов Дейкстры, Флойда — Уоршелла и прочих методов.

Где применяются графы:

• Представление потока вычислений.

• Распределение ресурсов в операционной системе.

• Моделирование дружеских связей и взаимодействий между пользователями социальных сетей.

• Оптимизация дорожных сетей, планирования маршрутов, управления транспортным движением и GPS-навигации.

• Представление биохимических сетей, геномных данных и анализа взаимодействия белков в молекулярной биологии.

• Отражение синтаксических и семантических отношений между словами в тексте.

• Бронирование номеров в гостиницах.

Заключение

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