Структуру данных можно разработать с нуля или взять уже готовую. Их много, но мы разбёрем 10 самых популярных.
Что такое структуры данных
Структура данных нужна для того, чтобы собирать и организовывать информацию так, чтобы ей было удобно пользоваться. Структура в программировании — это информации, связанная определённым образом. Массив данных — это тоже структура.
Данные в структуре можно добавлять, забирать, организовывать, проводить их анализ. У каждой структуры свои алгоритмы, которые пишут программисты. Алгоритмы можно взять готовые или создать свои.
Главное свойство структур данных в том, что у любой единицы данных должно быть чёткое место, по которому её можно найти. Как определяется это место и как происходит поиск, зависит от конкретной структуры.
Характеристики структур данных следующие:
- Данные в памяти представлены определённым образом, который однозначно позволяет определить структуру.
- Чаще всего внутрь структуры можно добавить элемент или извлечь оттуда. Это свойство не постоянное — бывают структуры, которые нельзя изменять после создания.
- Существуют алгоритмы, которые позволяют взаимодействовать с этой структурой.
При этом данных необязательно должно быть много. Массив из одного элемента — уже структура данных.
Материал по теме:
Что такое динамические массивы данных
и где они встречаются в обычной жизни
Зачем нужны структуры данных
Структуры нужны, чтобы упорядочивать, искать, анализировать и использовать данные с применением алгоритмов программирования.
Фактически использование структур данных в программировании начинается ещё с задания переменной. Формат переменной — определённая структура данных, так как в память переменная записывается конкретным способом. Но на практике программисты работают с другими структурами, которые объединяют в себе разные переменные и типы данных. Далее приведем описание и классификацию основных структур данных, чтобы было удобнее в них разобраться.
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 — что связи нет. Если у связей, то есть рёбер графа, есть вес, он как раз может быть помещён в ячейку
Как применяют графы:
- Для хранения информации, связанной друг с другом сложными соотношениями.
- Для анализа соотносящейся друг с другом информации.
- Для построения маршрута из точки А в точку Б.
Структуру данных для работы выбирают в зависимости от задачи. Если нужно что-то простое, подойдёт обычный массив. Когда требуется создать очередь или историю запросов, выбирают связный список или очередь. Если нужен поиск и сортировка, поможет двоичное дерево. Именно поэтому важно знать все типы данных в программировании, чтобы подбирать оптимальный в любой ситуации.
Подпишитесь на наш ежемесячный дайджест статей —
а мы подарим вам полезную книгу про обучение!
Читать также:
