Машинное представление связных линейных списков

Связные линейные списки

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

Графически связи в списках удобно изображать с помощью стрелок. Если компонента не связана ни с какой другой, то в поле указателя записывают значение, не указывающее ни на какой элемент. Такая ссылка обозначается специальным именем – nil.

На рис. 6.1 приведена структура односвязного списка. В нем поле INF является информационным, поле NEXT – указатель на следующий элемент списка. Каждый список должен иметь особый элемент, называемый указателем начала списка или головой списка, который по формату обычно отличен от остальных элементов. В поле указателя последнего элемента списка находится признак nil, свидетельствующий о конце списка.

Рис. 6.1. Структура односвязного списка.

Обработка односвязного списка не всегда удобна, т.к. отсутствует возможность продвижения в противоположную сторону. Такую возможность обеспечивает двухсвязный список, каждый элемент которого содержит указатель на следующий и предыдущий элементы списка. Структура линейного двухсвязного списка показана на рис. 6.2. Наличие двух указателей в каждом элементе усложняет список и приводит к дополнительным затратам памяти, но в то же время обеспечивает более эффективное выполнение некоторых операций над списком.

Рис. 6.2. Структура двухсвязного списка.

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

Рис. 6.3. Структура кольцевого двухсвязного списка.

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

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