Организация списков.

Преимущества динамической памяти становятся особенно очевидными при организации динамических структур

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

Элементы динамической структуры связаны через адреса (стеки, очереди, деревья, сети и т.д.). Основой моделирования таких структур являются списки.

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

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

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

Структура элемента линейного однонаправленного списка представлена на рисунке.

Следует рассмотреть разницу в порядке обработки элементов массива и списка.

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

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