Односвязные циклические списки

Циклически связанный список (сокращенно – циклический список) обладает той особенностью, что поле связи его последнего элемента не содержит значения nil, а указывает на первый узел списка. В целях удобства обработки в структуру циклического списка включают специальный узел с особым содержанием информационного поля (на рис. 29 это поле заштриховано), называемый головой списка или “сторожем”. Голова списка является дополнительным элементом. Назначение этого элемента состоит в том, чтобы отмечать точку входа в циклический список, а также упростить включение узлов в начало списка и исключение узлов из начала списка. На рис. 29 показана структура односвязного циклического списка с головным элементом.

Рис. 29. Структура односвязного циклического списка с головным узлом

Элемент хранения односвязного циклического списка описывается следующим образом:

Type PList=^List; List= record info: word; link: pList; end;	{ указатель на узел списка } { описание узла списка } { информационное поле узла } { поле связи узла }
Var head: PList;	{ указатель на «голову» списка }
p: Plist;	{ вспомогательный указатель }

Выполнение условия head = nil означает, что односвязный циклический список не существует. Выполнение условия head ^. link = head означает, что односвязный циклический список существует, но является пустым, т.е. содержит только головной элемент. Пустой циклический список с головным элементом представляется структурой элементарного кольца (рис. 30).

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

Односвязные циклические списки можно использовать для реализации линейных структур, таких как очереди, стеки, списки произвольного вида. При создании очереди новый узел включается в “хвост” списка, т.е. “перед” головным элементом (рис. 31). При создании стека новый узел включается в начало списка, т.е. непосредственно “за” головным элементом (рис. 32).

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

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

Ниже приведена процедура создания односвязного циклического списка из n узлов.

Procedure Create_Cicl(var head: PList; n: byte); var p: PList; i: byte; begin new(head); head^.link:=head;	{ head – указатель на голову списка } { n – количество узлов в списке }     { создание элементарного кольца }
for i:=1 to n do begin	{ cоздание циклического списка из n узлов }
new(p);	{ создание узла списка }
readln(p^.info);	{ заполнение информационного поля узла }
p^.link:=head^.link;	{ установка связи между вставленным узлом и cписком}
head^.link:=p;	{ обновление поля связи головного узла }
end; end;

Т.к. в циклическом списке каждый элемент, в том числе первый и последний, имеют предшественника и последователя (“перед” первым элементом и “за” последним элементом находится голова), все n элементов списка создаются и включаются в список одинаково (см. процедуру Create_Cikl). Каким образом включаются узлы в список при выполнении процедуры Create_Cikl: “за” головным узлом или “перед” ним? Исключение первого или последнего узла циклического списка также не имеет никаких особенностей за счет использования головного элемента. Операции включения / исключения узлов в список произвольного вида, реализованный в виде циклического списка, выполняются так же, как в нецикличесом списке.

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

...
if head <> nil then begin	{ список существует? }
p:=head^.link;	{ установить вспомогательный указатель }
while (p<> head) and (p^.info<> значение) do < тело цикла >	{ поиск }
end;
...

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

Указатель на головной элемент циклического списка не изменяет своего значения при выполнении любых операций над элементами списка, за исключением разрушения списка. При разрушении следует освободить области памяти, занятые элементами хранения узлов списка и головного элемента, после чего список прекращает свое существование (указатель head следует установить равным NIL).