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

На рис. 5.1 приведена структура односвязного списка. На нем

поле INF - информационное поле, данные, NEXT - указатель на сле-

дующий элемент списка. Каждый список должен иметь особый элемент,

называемый указателем начала списка или головой списка, который

обычно по формату отличен от остальных элементов. В поле указате-

ля последнего элемента списка находится специальный признак nil,

свидетельствующий о конце списка.

 

┌─────────────┬─┐ ┌────┬────┐ ┌────┬────┐ ┌────┬────┐

│голова списка│ ┼──>│INF │NEXT┼────>│INF │NEXT┼──>│INF │nil │

└─────────────┴─┘ └────┴────┘ ... └────┴────┘ └────┴────┘

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

Однако, обработка односвязного списка не всегда удобна, так

как отсутствует возможность продвижения в противоположную сторо-

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

элемент которого содержит два указателя: на следующий и предыду-

щий элементы списка. Структура линейного двухсвязного списка при-

ведена на рис. 5.2, где поле NEXT - указатель на следующий эле-

мент, поле PREV - указатель на предыдущий элемент. В крайних эле-

ментах соответствующие указатели должны содержать nil, как и по-

казано на рис. 5.2.

Для удобства обработки списка добавляют еще один особый эле-

мент - указатель конца списка. Наличие двух указателей в каждом

элементе усложняет список и приводит к дополнительным затратам

памяти, но в то же время обеспечивает более эффективное выполне-

ние некоторых операций над списком.

┌─┬─────────────┐ ┌───────────────┬─┐

│ │голова списка│ │указатель конца│ │

└┼┴─────────────┘ └───────────────┴┼┘

│ ┌────┬───┬────┐ ┌────┬───┬────┐ └─>┌────┬───┬────┐

└>│ │ │ ─┼────>│ │ │ ─┼───>│ │ │ │

│nil │INF│NEXT│ │PREV│INF│NEXT│ │PREV│INF│ nil│

│ │ │ │<────┼─ │ │ │<───┼─ │ │ │

└────┴───┴────┘ ... └────┴───┴────┘ └────┴───┴────┘

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

Разновидностью рассмотренных видов линейных списков является

кольцевой список, который может быть организован на основе как

односвязного, так и двухсвязного списков. При этом в односвязном

списке указатель последнего элемента должен указывать на первый

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

ответствующие указатели переопределяются, как показано на

рис.5.3.

При работе с такими списками несколько упрощаются некоторые

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

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

попасть в бесконечный цикл.

┌─┬─────────────┐

│ │голова списка│

└┼┴─────────────┘ ┌────────────────┐

┌───┘ │ │

└>┌────┬───┬────┐ ┌────┬───┬────┐ └>┌────┬───┬────┐│

┌>│ │ │ ─┼─> ─>│ │ │ ─┼───>│ │ │ ─┼┼┐

│ │PREV│INF│NEXT│ ... │PREV│INF│NEXT│ │PREV│INF│NEXT│││

│┌┼─ │ │ │<─ <─┼─ │ │ │<───┼─ │ │ │││

││└────┴───┴────┘ └────┴───┴────┘ └────┴───┴────┘││

│└──────────────────────────────────────────────────────────┘│

└────────────────────────────────────────────────────────────┘

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

В памяти список представляет собой совокупность дескриптора

и одинаковых по размеру и формату записей,

размещенных произвольно в некоторой области памяти и связанных

друг с другом в линейно упорядоченную цепочку с помощью указате-

лей. Запись содержит информационные поля и поля ука-

зателей на соседние элементы списка, причем некоторыми полями ин-

формационной части могут быть указатели на блоки памяти с

дополнительной информацией, относящейся к элементу списка. Деск-

риптор списка реализуется в виде особой записи и содержит такую

информацию о списке, как адрес начала списка, код структуры, имя

списка, текущее число элементов в списке, описание элемента и

т.д., и т.п. Дескриптор может находиться в той же области памяти,

в которой располагаются элементы списка, или для него выделяется

какое-нибудь другое место.