Простейшие типы данных

1.4 Список

Список является более сложной структурой хранения, в которой элементы имеют явные связи. В списке элементы структур данных размещаются не обязательно в смежных областях памяти. Каждый элемент структуры данных содержит по крайней мере два поля. Одно поле — основное содержит данные этого элемента или указатель на данные, а другое поле предназначено для размещения указателя на следующий элемент. Оконечный элемент структуры данных в поле указателя содержит признак конца списка (NULL). Элемент структуры данных, в свою очередь, тоже может быть структурой, хранимой в виде списка. Различают однонаправленные списки, двунаправленные списки, циклические списки. Число элементов списка может изменяться. Учитывая наличие явных связей между элементами списка, иногда используют термины цепной список или связный список. Список, отражающий отношение соседства между элементами (у каждого элемента списка могут быть только один предыдущий и один последующий элементы), называется линейным. Любой другой список называется нелинейным. Однонаправленный список является простейшей формой списка.

Массив

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

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

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

Физически список реализуется как совокупность дескриптора списка и элементов, размещенных в оперативной памяти или на внешних запоминающих устройствах (ВЗУ) и связанных друг с другом в цепочку с помощью указателей. Дескриптор обычно реализуется в виде записи и может содержать следующую информацию о списке;

тип структуры;
имя списка;
указатель (адрес) начала списка;
текущее число элементов;
описание элемента (длина, тип и т.п.).

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

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

Возможна организация списка и в смежной области памяти. В этом случае все элементы структуры данных имеют один и тот же тип, а число возможных элементов ограничено размерами области памяти. На рис. приведен пример цепного списка, размещенного в одной сплошной области памяти (указатель списка размещен в другой области и содержит адрес списка). Элементами данных являются буквы. Последовательность букв, размещенных в списке, образует слово АЗБУКА. В качестве указателей использованы индексы.

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