Структура данных

Структура данных в программировании — это объект-контейнер, в котором хранится информация. Данные внутри контейнера структурированы по особой системе — она различается в зависимости от вида структуры. Так разработчики оптимизируют доступ к информации.

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

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

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

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

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

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

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

Описание структуры данных можно условно поделить на интерфейс и реализацию. Интерфейс — это набор операций, который описывает поведение конкретной структуры. То есть это то, что можно сделать с конкретной структурой данных. А реализация — то, как данные структурированы внутри.

Кроме того, типичная структура данных отвечает нескольким критериям:

• корректность, то есть грамотная реализация своего технического описания;
• пространственная сложность — реализация должна занимать минимум места;
• временная сложность — операции должны выполняться за минимум времени.

«Минимум места» и «минимум времени» могут различаться для разных структур. Это нормально: у каждой из них свое назначение и оптимальный способ использования.

Какими бывают структуры данных

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

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

Ниже мы коротко расскажем о наиболее популярных структурах данных: их особенностях, операциях с ними и ситуациях, когда их следует применять.

Массивы

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

Индексы идут последовательно. Это целые числа, последовательность которых начинается с 0.

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

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

Как правило, в массиве могут лежать данные только одного типа. Например, массив чисел или массив строк.

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

Применение. Массивы применяют в большинстве ситуаций, где требуется организованное хранение данных. Не используют их только в сложных структурах: там логичнее будет применить другой формат. Но и тут массивы нужны как строительные «кирпичики» для реализации более комплексных структур.

Очереди

Очередь похожа на массив. Это тоже линейная структура, состоящая из последовательности элементов. Разница в том, что доступ к этим элементам возможен только по принципу FIFO: First In, First Out. Это значит, что из очереди можно быстро и легко извлечь элемент, который расположен в самом ее начале и находится в ней дольше всего. А вот операций для доступа с конца или из середины может вообще не быть. Добавляются же элементы, наоборот, только в конец — как с реальной очередью в магазине.

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

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

Стеки

Стек — структура, обратная очереди. Это последовательность, в которой доступ работает по принципу LIFO: Last In, First Out. Элементы добавляются в конец, а быстро получить и извлечь их можно опять же с конца. То есть чем позже элемент добавили в стек, тем легче до него добраться.

Английское слово stack означает «стопка», например, стопка бумаг. Так можно представить и стек: как стопку бумаг, где самый верхний элемент берется первым.

Операции. Среди операций специально для стеков — так называемый push, то есть добавление элемента в конец, и pop — извлечение элемента из конца. Извлечение означает, что элемент удаляется из стека, но возвращается как значение.

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

Применение. Стек используется при выделении памяти программам и процессам. Функции, работающие внутри программы, как бы «укладываются» в системный стек.  Популярное выражение stack overflow — это распространенная ошибка, возникающая, когда стек переполняется из-за неправильного использования памяти. Чаще всего такое бывает при рекурсии.

Еще один вариант применения стека — история просмотров: доступ к данным, которые человек просмотрел последними, проще.

Деки

Деками называют двусторонние очереди: они объединяют возможности и очереди, и стека. Такие структуры данных могут работать и по принципу FIFO, и по принципу LIFO. Доступ к элементам возможен с любого конца.

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

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

Связанные списки

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

Сами элементы, в отличие от массива, хранятся отдельно друг от друга. У них нет номеров. Последовательность достигается исключительно за счет указателей «следующий» и «предыдущий». Последний элемент будет указывать на «пустое» значение.

У односвязных списков есть ссылки только на следующий элемент, у двусвязных — и на следующий, и на предыдущий. Их еще называют однонаправленными или двунаправленными. Есть и круговые списки — они закольцовываются, и последний их элемент указывает на первый.

Первый элемент называется головой списка, последний — хвостом.

Операции. В список можно добавить элемент — в голову, хвост или заданный участок. Также можно обновить значение элемента или удалить его, провести поиск по структуре данных. Также есть операция-проверка, пуст ли список. Доступ к следующему элементу возможен с помощью указателя next, к предыдущему — prev.

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

Множества

Множество — еще одна линейная структура данных. Ее особенность в том, что элементы не имеют четкого порядка, зато уникальны по значению. Ее можно представить не как последовательность или список, а как «облако тегов»: неупорядоченный набор уникальных значений. Это определение близко к математическому понятию множества. И работают с ним так же: не сортируют и не структурируют, но хранят, получают и анализируют данные.

Множество еще называют сетом. По-английски название звучит как Set.

Операции. Характерные для этой структуры данных операции рассчитаны на работу с двумя множествами. Например, это операции объединения множества, сравнения, поиска пересечений между двумя сетами. Похоже на круги Эйлера, но программно реализованные. 

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

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

Карты

По-английски эта структура данных называется Map. Ее еще называют ассоциативным массивом или словарем. Она действительно похожа на массив, но вместо упорядоченных числовых индексов в ней используются «ключи» — заданные пользователем числа или строки. Весь массив — это набор пар из ключей и значений.

Можно представить эту структуру данных как телефонный справочник. Ключ — это имя, по которому человек ищет нужный номер. А само значение — собственно, номер телефона.

Разработчик сам задает ключи или генерирует их автоматически. Часто ключи строковые: это облегчает понимание и поиск информации.

Обычно в ассоциативных массивах можно хранить данные разных типов. Ключи тоже могут различаться.

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

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

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

«name: Ivan,

phone: +79991234567,

isAgree: true»

Ключи name, phone и isAgree описывают, что именно передают: имя, телефон и наличие согласия на получение сообщений. А Ivan, true и номер — уже значения, которые приняли эти параметры.

Хэш-таблицы

Эта структура данных похожа на ассоциативный массив и иногда реализуется через него. Разница в том, что ключ для каждого значения задается автоматически с помощью специальной формулы — хэш-формулы. Эта формула применяется к самому значению — в результате генерируется ключ, основанный на нем.

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

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

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

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

Графы

Граф — нелинейная структура организации данных, которая состоит из «вершин» и «ребер» между ними. Каждая вершина — это значение, а ребра — пути, которые соединяют между собой вершины. Получается своеобразная «сетка», похожая на карту дорог или созвездие.

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

Также существуют взвешенные графы, у ребер которых есть «вес» — то или иное значение. Например, в карте дорог весом ребра-дороги можно назвать его длину.

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

Операции. С этими структурами есть базовые операции: добавление вершины или ребра, отображение вершины или графа целиком, оценка «стоимости» обхода взвешенного графа и так далее.

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

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

Деревья

Деревья можно назвать частным случаем графов. Это тоже структуры из вершин и ребер, но имеющие древовидный формат. Вершины деревьев называются узлами. От одного узла может отходить несколько вершин-потомков, но предок у каждого узла может быть только один. Так и получается древовидная иерархическая структура.

В программировании применяют несколько видов деревьев. Большинство из них реализуют с помощью графов.

• Бинарные деревья поиска — самый распространенный формат деревьев. У каждого узла может быть не более двух потомков. Если значение узла-потомка меньше предка, он располагается слева. Если равно или больше — справа. С помощью таких деревьев удобно сортировать данные и искать в них нужное значение с помощью бинарного поиска.
• Префиксные деревья, они же нагруженные деревья или боры — это деревья, которые хранят данные «по цепочке». Узлы-предки — префиксы, которые нужны, чтобы перейти к потомкам. При прохождении дерева «собираются» полные данные. Например, в каждом узле — буква. При прохождении от начала до конца получаются слова. Обычно такие деревья используют для хранения повторяющихся данных или, например, для реализации автодополнения при вводе.
• Двоичные кучи — двоичные деревья, заполненные целиком. У каждого узла два потомка. Потомки в зависимости от типа дерева должны быть строго больше предков или меньше либо равны им.

Также существуют N-арные деревья, красно-черные деревья, AVL-деревья, сбалансированные, 2-3-4-деревья и так далее.

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

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

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

Узнать больше о программировании и хранении данных вы можете на наших курсах. Записывайтесь — сделайте первый шаг к новой популярной профессии.