1 Сущность и понятие динамической структуры список

Чтобы лучше понять, что же такое динамические структуры данных, сперва рассмотрим отличия динамических структур данных от статических.

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

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

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

• лёгкость добавления и удаления элементов;

• размер ограничен только объёмом памяти компьютера и разрядностью указателей;

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

Вместе с тем связное представление не лишено и недостатков, основные из которых:

• сложность определения адреса элемента по его индексу;

• на поля-указатели расходуется дополнительная память;

• элементы связной структуры могут быть расположены в памяти разреженно, что окажет негативный эффект на кэширование процессора;

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

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

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