При выполнении рабочих задач программистам приходится сталкиваться со структурами данных: работать с ними или разрабатывать с нуля. Таких структур много, но десять из них встречаются на практике чаще всего.
Что такое структуры данных
Структура данных — это способ организации информации для более эффективного использования. В программировании структурой обычно называют набор данных, связанных определённым образом. Например, массив — это структура.
Со структурой можно работать: добавлять данные, извлекать их и обрабатывать, например изменять, анализировать, сортировать. Для каждой структуры данных — свои алгоритмы. Работа программиста — правильно выбирать уже написанные готовые либо писать свои.
Главное свойство структур данных в том, что у любой единицы данных должно быть чёткое место, по которому её можно найти. Как определяется это место и как происходит поиск, зависит от конкретной структуры.
Характеристики структур данных следующие:
● Данные в памяти представлены определённым образом, который однозначно позволяет определить структуру.
● Чаще всего внутрь структуры можно добавить элемент или извлечь оттуда. Это свойство не постоянное — бывают структуры, которые нельзя изменять после создания.
● Существуют алгоритмы, которые позволяют взаимодействовать с этой структурой.
При этом данных необязательно должно быть много. Массив из одного элемента — уже структура данных.
Материал по теме:
Что такое динамические массивы данных
и где они встречаются в обычной жизни
Зачем нужны структуры данных
Структуры нужны, чтобы упорядочивать, искать, анализировать и использовать данные с применением алгоритмов программирования.
Фактически использование структур данных в программировании начинается ещё с задания переменной. Формат переменной — определённая структура данных, так как в память переменная записывается конкретным способом. Но на практике программисты работают с другими структурами, которые объединяют в себе разные переменные и типы данных. Далее приведем описание и классификацию основных структур данных, чтобы было удобнее в них разобраться.
10 основных структур данных
1. Массив (Array)
Одна из самых простых структур данных, которая встречается чаще всего. Именно на массивах основаны многие другие структуры данных: списки, стеки, очереди.
Для простоты восприятия можно считать, что массив — это таблица. Каждый его элемент имеет индекс — «адрес», по которому этот элемент можно извлечь. В большинстве языков программирования индексы начинаются с нуля. То есть первый элемент массива имеет индекс не [1], а [0]. Данные в массиве можно просматривать, сортировать и изменять с помощью специальных операций.
Массивы бывают двух видов:
● Одномерные
У каждого элемента только один индекс. Можно представить это как строку с данными, где одного номера достаточно, чтобы чётко определить положение каждой переменной.
● Многомерные
У каждого элемента два или больше индексов. По сути, это комбинация из нескольких одномерных массивов, то есть вложенная структура.
Основное отличие между одномерным и многомерным массивом ― их размерность и способ организации данных. Одномерный массив ― простая линейная структура данных, многомерный ― более сложная структура данных с несколькими измерениями
Как применяют массивы:
● В качестве блоков для более сложных структур данных. Массивы предусмотрены в синтаксисе большинства языков программирования, и на их основе удобно строить другие структуры.
● Для хранения несложных данных небольших объёмов.
● Для сортировки данных.
2. Динамический массив (Dynamic array)
В классическом массиве размер задан заранее — мы точно знаем, сколько в нём индексов. А динамический массив — это тот, у которого размер может изменяться. При его создании задаётся максимальная величина и количество заполненных элементов. При добавлении новых элементов они сначала заполняются до максимальной величины, а при превышении сразу создаётся новый массив, с большей максимальной величиной.
Элементы в динамический массив можно добавлять без ограничений и куда угодно. Однако, если добавлять их в середину, остальные придётся сдвигать, что занимает много времени. Поэтому лучше всего динамический массив работает при добавлении элементов в конце.
Как применяют динамические массивы:
● В качестве блоков для структур данных.
● Для хранения неопределённого количества элементов.
3. Связный список (Linked list)
Ещё одна базовая структура данных, которую, как и массивы, используют для реализации других структур. Связный список — это группа из узлов. В каждом узле содержатся:
● Данные.
● Указатель или ссылка на следующий узел.
● В некоторых списках — ещё и ссылка на предыдущий узел.
В итоге получается список, у которого есть чёткая последовательность элементов. При этом сами элементы более разрозненны, чем в массиве, поскольку хранятся отдельно. Быстро перемещаться между элементами списка помогают указатели.
Так устроен связный список
Как применяют связные списки:
● Для построения более сложных структур данных.
● Для реализации файловых систем.
● Для формирования хэш-таблиц.
● Для выделения памяти в динамических структурах данных.
4. Стек (Stack)
Эта структура данных позволяет добавлять и удалять элементы только из начала. Она работает по принципу LIFO — Last In, First Out (англ. «последним пришёл — первым ушёл»). Последний добавленный в стек элемент должен будет покинуть его раньше остальных.
Просмотреть стек можно целиком, а работать — только с вершиной. Для этого надо удалить или добавить последний элемент
Как применяют стеки:
● Для реализации рекурсии.
● Для вычислений постфиксных значений.
● Для временного хранения данных, например истории запросов или изменений.
5. Очередь (Queue)
Этот вид структуры представляет собой ряд данных, как и стек. Но в отличие от него она работает по принципу FIFO — First In, First Out (англ. «первым пришёл — первым ушёл»). Данные добавляют в конец, а извлекают из начала.
В этой структуре данных всегда работают только с первым элементом. Остальные в это время «ждут своей очереди»
Бывают неклассические, двусторонние очереди. В них можно добавлять элементы и извлекать их из начала и конца структуры. Элементы посередине недоступны.
Как применяют очереди:
● Для реализации очередей, например на доступ к определённому ресурсу.
● Для управления потоками в многопоточных средах.
● Для генерации значений.
● Для создания буферов.
6. Множество (Set)
В отличие от предыдущих базовых структур, во множестве данные не упорядочены. Они хранятся группой, их нельзя структурировать и в некоторых случаях нельзя сортировать. Зато с ними можно работать как с классическими математическими множествами: объединять, искать пересечения, вычислять разность и смотреть, является ли одно множество подмножеством другого.
Обычно во множество помещают объекты, у которых есть что-то общее. Важны свойства объектов, а их порядок значения не имеет
Как применяют множества:
● Для поддержания множества уникальных элементов.
● Для хранения данных, которые не нужно сортировать.
● Для сравнения, объединения наборов данных и других операций с ними.
7. Карта (Map)
Её ещё называют ассоциативным массивом или словарём. Данные здесь хранятся в паре «ключ/значение», причем каждый ключ уникален, а вот значения могут повторяться. То есть определённому уникальному ключу всегда соответствует конкретное значение.
Зная ключ, данные в Map можно искать быстрее, чем в других структурах
Как применяют Карту:
● Для быстрого поиска данных.
● Для создания баз, в которых нужно хранить уникальное соответствие между двумя множествами значений. Их помещают в ключ, и структура проверяет, чтобы ключ не повторялся.
Частный случай map — это hash-map, или хэш-таблица. В ней есть ключи и значения, а для их реализации добавляются индексы. Специальная хэш-функция позволяет по ключу вычислить индекс, чтобы найти нужные данные.
Если знать ключ, с помощью хэш-функции можно вычислить индекс и найти данные
Когда в хэш-таблицу что-то вносят, то вписывают ключ и данные. Далее функция хэширует ключ, переводит его в число и записывает данные в ячейку, соответствующую этому числу. Когда нужно запросить данные, снова вводят ключ — и по нему хэш-функция находит нужные данные.
8. Двоичное дерево поиска (Binary search tree)
Дерево — это структура, данные в которой лежат в узлах. У каждого узла могут быть один или несколько дочерних и только один родитель, то есть они расходятся, как ветви дерева:
В структуре дерева данные хранятся в узлах
Деревья бывают разных типов, но наиболее распространены двоичные деревья поиска. У них есть следующие особенности:
● У каждого узла не больше двух дочерних.
● Если новое значение меньше, оно становится левым дочерним либо дочерним левого дочернего.
● Если значение больше, оно становится правым дочерним или дочерним правого дочернего.
Как применяют двоичные деревья:
● Для быстрого поиска данных.
● Для хранения данных в отсортированном виде с возможностью быстро их добавлять и удалять.
9. Префиксное дерево (Trie)
Другие названия этой структуры данных — Бор и нагруженное дерево. Данные в нём хранятся последовательно: каждый узел — это префикс, по которому находятся следующие узлы.
Как применяют префиксные деревья:
● Для хранения данных, которые нужно выдавать по цепочке. Например, слова для функции автозаполнения в телефоне: в зависимости от одной набранной буквы дерево выдаёт следующие.
● Для хранения данных, у которых есть повторяющиеся участки. Например IP-адресов.
Пример хранения слов в префиксном дереве. Звёздочки означают конец префикса
10. Граф (Graph)
Граф — это более общий случай дерева. Иногда деревья называют ациклическими графами. Отличий у этих структур данных два:
● В графе возможны циклы, то есть «ребёнок» может быть «родителем» для того же элемента.
● Рёбра тоже могут нести смысловую нагрузку, то есть нужно сохранять их значения.
Графы бывают ориентированные и неориентированные. У первых рёбра между узлами имеют направление, так что порядок элементов важен. У вторых направлений нет, и элементы можно читать и обходить в любом порядке.
У ориентированных графов важен порядок элементов, у неориентированных ― элементы можно менять местами
Графы часто представляют в виде матрицы смежности.
Здесь каждая строка или столбец — узел. 1 в ячейке означает, что между узлами есть связь, 0 — что связи нет. Если у связей, то есть рёбер графа, есть вес, он как раз может быть помещён в ячейку
Как применяют графы:
● Для хранения информации, связанной друг с другом сложными соотношениями.
● Для анализа соотносящейся друг с другом информации.
● Для построения маршрута из точки А в точку Б.
Структуру данных для работы выбирают в зависимости от задачи. Если нужно что-то простое, подойдёт обычный массив. Когда требуется создать очередь или историю запросов, выбирают связный список или очередь. Если нужен поиск и сортировка, поможет двоичное дерево. Именно поэтому важно знать все типы данных в программировании, чтобы подбирать оптимальный в любой ситуации.
Дайджест блога: ежемесячная подборка лучших статей от редакции
Читать также:
