Циклический двунаправленный список

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

Рисунок 3.5 – Циклический двусвязный список

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

– вставка элемента;

– просмотр;

– поиск;

– удаление элемента.

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

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

procedure Ins_CicleDubleList(DataElem: TypeData;

var ptrHead, ptrCurrent: PElement);

{Вставка элемента в циклический двунаправленный список

справа от элемента, на который указывает ptrCurrent}

var

ptrAddition: PElement; {вспомогательный указатель}

begin

New(ptrAddition);

ptrAddition^.Data := DataElem;

if ptrHead = nil then begin {список пуст}

{создаем первый элемент списка}

ptrAddition^.Next := ptrAddition; {петля из 1 элемента}

ptrAddition^.Last := ptrAddition;

ptrHead := ptrAddition;

end else begin {список не пуст}

{вставляем элемент списка справа от элемента,}

{на который указывает ptrCurrent}

ptrAddition^.Next := ptrCurrent^.Next;

ptrCurrent^.Next := ptrAddition;

ptrAddition^.Last := ptrCurrent;

ptrAddition^.Next^.Last := ptrAddition;

end;

ptrCurrent := ptrAddition;

end;

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

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

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

Операция удаления элемента также осуществляется во многом аналогично удалению из циклического однонаправленного списка.

procedure Del_CicleDubleList(var ptrHead, ptrCurrent: PElement);

{Удаление элемента из циклического двунаправленного списка}

var

ptrAddition: PElement; {дополнительный указатель}

begin

if ptrCurrent <> nil then begin {вх.параметр корректен}

if ptrHead^.Next <> ptrHead then begin

{Если удаляемый элемент не единственный в списке}

ptrAddition := ptrCurrent^.Next;

ptrCurrent^.Last^.Next := ptrCurrent^.Next;

ptrCurrent^.Next^.Last := ptrCurrent^.Last;

if ptrHead = ptrCurrent then {удаляем первый}

ptrHead := ptrCurrent^.Next;

dispose(ptrCurrent);

ptrCurrent := ptrAddition;

end else begin

ptrHead:=nil;

dispose(ptrCurrent);

ptrCurrent:=nil;

end;

end;

end;

Листинг 3.15 – Процедура удаления элемента из циклического двусвязного списка

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