Кольцевой односвязный список
Кольцевой односвязный список получается из обычного односвязного списка путем присваивания указателю последнего элемента списка значение указателя начала списка (рис 3.3).
Простейшие операции, производимые над односвязными списками
1) Вставка в начало односвязного списка.
Надо вставить в начало односвязного списка элемент с информационным полем D. Для этого необходимо сгенерировать пустой элемент (P=GetNode). Информационному полю этого элемента присвоить значение D (INFO(P)=D), значению указателя на этот элемент присвоить значение указателя на начало списка (Ptr(P) = Lst), значению указателя начала списка присвоить значение указателя P (Lst = P).
Реализация на Паскале:
type
PNode = ^TNode;
TNode = record
Info: Integer; {тип элементов списка - может быть любым}
Next: PNode;
end;
var
Lst: PNode; {указатель на начало списка}
P: PNode;
Вставка в начало
New(P); {создание нового элемента}
P^.Info:=D;
P^.Next:=Lst; {P указывает на начало списка, но Lst не указывает на P - новое начало}
Lst:=P; {Lst указывает на новое начало списка}
2) Удаление элемента из начала односвязного списка.
Надо удалить первый элемент списка, но запомнить информацию, содержащуюся в поле Info этого элемента. Для этого введем указатель P, который будет указывать на удаляемый элемент (P = Lst). В переменную X занесем значение информационного поля Info удаляемого элемента (X=Info(P)). Значению указателя на начало списка присвоим значение указателя следующего за удаляемым элемента (Lst = Ptr(P)). Удалим элемент (FreeNode(P)).
Реализация на Паскале:
Удаление из начала
P:=Lst;
X:=P^.Info;
Lst:=P^.Next;
Dispose(P); {Удаляет элемент из динамической памяти}