2.2. Список

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

Однонаправленный список является простейшей формой списка.

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

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

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

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

• тип структуры;

• имя списка;

• указатель (адрес) начала списка;

• текущее число элементов;

• описание элемента (длина, тип и т.п.).

Вместо дескриптора можно использовать только указатель.

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

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

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

Рисунок 4 - Цепной список в смежной области памяти

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

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