двусвязные)

Примечание

Раздел находится в процессе наполнения!

Введение

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

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

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

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

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

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

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

Массив (Array)

Одна из самых простых структур данных, которая встречается чаще всего. Именно на массивах основаны многие другие структуры данных: списки, стеки, очереди.

Для простоты восприятия можно считать, что массив — это таблица. Каждый его элемент имеет индекс — «адрес», по которому этот элемент можно извлечь. В большинстве языков программирования индексы начинаются с нуля. То есть первый элемент массива имеет индекс не [1], а [0]. Данные в массиве можно просматривать, сортировать и изменять с помощью специальных операций.

Массивы бывают двух видов:

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

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

Как применяют массивы:

В качестве блоков для более сложных структур данных. Массивы предусмотрены в синтаксисе большинства языков программирования, и на их основе удобно строить другие структуры.
Для хранения несложных данных небольших объёмов.
Для сортировки данных.

Динамический массив (Dynamic array)

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

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

Как применяют динамические массивы:

В качестве блоков для структур данных.
Для хранения неопределённого количества элементов.

Связный список (Linked list)

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

Данные.
Указатель или ссылка на следующий узел.
В некоторых списках — ещё и ссылка на предыдущий узел.

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

Как применяют связные списки:

Для построения более сложных структур данных.
Для реализации файловых систем.
Для формирования хэш-таблиц.
Для выделения памяти в динамических структурах данных.