Если значение указателя последнего звена линейного односвязного списка заменить с nil (или NULL) на адрес ведущего звена, то линейный список превратится в односвязный кольцевой список.
Для двусвязного списка, кроме того, нужно заменить с nil на адрес последнего звена значение второго указателя в ведущем звене. Получится двусвязный кольцевой (циклический) список.
В односвязном кольцевом списке можно переходить от последнего звена к заглавному, а в двусвязном - еще и от заглавного к последнему.
Двусвязный кольцевой список выглядит так:
Кольцевой список, как и линейный, идентифицируется как единый программный объект указателем, например L2, значением которого является адрес заглавного звена.
Возможен другой вариант организации кольцевого списка:
Оба варианта сопоставимы по сложности. Для первого варианта проще выполняется вставка нового элемента как в начало списка (после заглавного звена), так и в конец - так как вставка звена в конец кольцевого списка эквивалентна вставке перед заглавным звеном, но каждый раз при циклической обработке списка нужно проверять, не является ли текущее звено заглавным (или не совпадает ли текущее звено с точкой начала обработки).
Рассмотрим операции с кольцевыми списками.
Отсутствие "последнего" звена приводит к ещё большему упрощению операций добавления и удаления, по сравнению с 1- и 2-связным линейным списком. Например, для 1-связного кольцевого списка в процедуре удаления отсутствует оператор if - проверка на существование звена, следующего за заданным (в кольцевом списке такое звено всегда есть). Такие же операторы отсутствуют в процедурах добавления и удаления звеньев для 2-связного кольцевого списка.
При циклической обработке кольцевого списка нужно учесть, что формально последнего звена нет.
Программа работы с двусвязным кольцевым списком на языке Паскаль
Type
rel2=^elem2;
elem2=record
next:rel1;
prev:rel2;
data:<Тип хранимых данных>
end;
list2=rel2;
procedure insert2(pred:rel2; info:<Тип>);
var
q:rel2;
begin
new(q); (* Создание нового звена *)
q^.data:=info;
q^.next:=pred^.next;
q^.prev:=pred^.next^.prev;
pred^.next.prev:=q;
pred^.next:=q
end;
При вставке в начало списка (после заглавного звена) нужно указать в качестве аргумента pred адрес заглавного звена, то есть указатель на список L2.
procedure delete2(del:rel2);
begin
del^.next^.prev:=del^.prev;
del^.prev^.next:=del^.next;
dispose(del);
end;
function search2(list:rel2; info:<Тип>; var point:rel2):boolean;
var
p,q:rel2;
b:boolean;
begin
b:=false;
point:=nil;
p:=list;
q:=p^.next;
while (p<>q) and (not b) do
begin
if q^.data=info then
begin
b:=true;
point:=q
end;
q:=q^.next
end;
search2:=b
end;
...
...
var
l2:list2;
r:rel2;
begin (* Создание заглавного звена *)
new(r);
r^.next:=r;
r^.pred:=r;
l2:=r;
...
...
end.
Процедуры работы с двусвязным кольцевым списком на языке Си++
Тип данных для кольцевого 2-связного списка такой же, как и для 2-связного линейного. То же самое справедливо для 1-связных списков. По типу звена списка нельзя судить о его архитектуре, можно - только о числе связей.
Добавление звена в произвольную позицию за ведущим звеном
void Insert(Link2* Pred,int data)
{
Link2* Loc=new Link2; // 1
Loc->Value=data; // 2
Loc->next=Pred->next; // 3
Loc->prev=Pred; // 4
Pred->next=Loc; // 5
Loc->next->prev=Loc; // 6
}
Удаление звена из любого места списка за ведущим звеном
void Delete2(Link2* Del)
{
Del->prev->next=Del->next; // 1
Del->next->prev=Del->prev; // 2
delete Del; // 3
}
Поиск
int Search(Link2* Start,Link2*& Find,int Key)
{
Link2* Cur=Start->next;
int Success=0;
while(Cur!=Start && !Success)
{
if(Cur->Value==Key)
{
Find=Cur;
Success=1;
break;
}
Cur=Cur->next;
}
return Success;
}
Прекращение поиска в случае неудачи происходит при достижении "текущим" указателем Cur точки начала поиска Start, т.е. при невыполнении условия в операторе while:
