Программирование  •  10 августа 2022  •  5 мин чтения

10 структур данных, которые должен знать каждый разработчик

При выполнении рабочих задач программистам приходится сталкиваться со структурами данных: работать с ними или разрабатывать с нуля. Таких структур много, но десять из них встречаются на практике чаще всего.
Сергей Савельев
Яндекс Практикум
Наставник на факультете Java, руководитель и разработчик в Яндекс Маркете
Лена Шпрингер
Яндекс Практикум
Редактор

Что такое структуры данных

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

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

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

Характеристики структур данных следующие:

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

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

● Существуют алгоритмы, которые позволяют взаимодействовать с этой структурой.

При этом данных необязательно должно быть много. Массив из одного элемента — уже структура данных.

Зачем нужны структуры данных

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

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

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 — что связи нет. Если у связей, то есть рёбер графа, есть вес, он как раз может быть помещён в ячейку.

Как применяют графы:

● Для хранения информации, связанной друг с другом сложными соотношениями.

● Для анализа соотносящейся друг с другом информации.

● Для построения маршрута из точки А в точку Б.

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

Поделиться 
Fri Sep 09 2022 22:34:19 GMT+0300 (Moscow Standard Time)