Двусвязный (двунаправленный) циклический список.

Односвязный (однонаправленный) циклический список.

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

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

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

Пример программыработыс двусвязным циклическим списком

Одна из возможных реализаций объекта для работы с двусвязным циклическим списком (создание и вывод списка, добавление элемента справа от текущего элемента, удаление элемента слева от текущего):

unit obj_type; { модуль описания объекта для обработки циклического двусвязного списка }

Interface

type

point=^element;

element= record

data: byte;

last, next: point;

end;

List= object

pcur: point;

procedure Init; { создание пустого списка }

procedure Create; { ввод данных и формирование списка }

procedure Current; { назначение текущего элемента }

procedure Output; { вывод списка }

procedure Add_right; { добавление элемента справа от текущего}

procedure Del_left; { удаление элемента слева от текущего }

end;

Implementation

procedure List.Init;

begin

pcur:= nil;

end;

procedure List.Create;

var

p, p1: point;

ans: char

begin

repeat

New( p);

writeln(‘ Данные: ’);

readln(p^. data);

if pcur<>nil then

begin

pcur^. next:= p;

p^. last:=pcur;

end

else

p1:=p;

pcur:= p;

writeln(‘ Продолжить ввод?(Д/Н) ’);

readln(ans);

until ans= ‘Н’;

pcur^. next:=p1;

p1^. last:=pcur;

end;

procedure List.Current;

var

p, pnt: point;

k: byte;

begin

clrscr;

writeln('Данные текущего элемента:');

readln(k);

p:=pcur;

pnt:=pcur;

repeat

if p^.data=k then

begin

pcur:=p;

break;

end;

p:=p^.next;

until p=pnt;

end;

procedure List.Output;

var

i: integer;

p: point;

begin

clrscr;

p:=pcur;

i:=1;

repeat

writeln(i,'-',p^ .data);

p:=p^. next;

i:=i+1;

until p=pcur;

readln;

end;

procedure List.Add_right;

var

p, pnt: point;

k: byte;

begin

clrscr;

writeln('Данные:');

readln(k);

New(p);

p^.data:=k;

p^.last:=pcur;

p^.next:=pcur^.next;

pnt:=pcur^.next;

pcur^.next:=p;

pnt^.last:=p;

end;

procedure List.Del_left;

var

p: point;

begin

if pcur^.next<>pcur then

begin

p:=pcur^.last;

pcur^.last:=p^.last;

p^.last^.next:=pcur;

Dispose(p);

end;

end;

end.

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