double arrow

Дважды связные списки


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

Рис. 1.4 Дважды связный список

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

Type pt=^elem; {Указатель на элемент списка}

Elem=Record

Data : Integer; {Поле данных}

Next :pt; {Указатель на следующий элемент списка}

Previous : pt; {Указатель на предыдущий элемент списка}

End;

Var first:pt; {Указатель на первый элемент списка}

Ниже показаны процедуры построения двусвязного списка, а также удаления элемента из него. На рис. 1.5 приведена схема удаления элемента из дважды связного списка. Здесь предполагается, что удаляемая ячейка не является ни первой, ни последней в списке. Сплошными линиями показаны указатели до удаления, а пунктирными – после удаления элемента. Сначала с помощью указателя поля previous определяется положение предыдущей ячейки. Затем в поле next этой ячейки устанавливается указатель на ячейку, предшествующую позиции р. Таким образом, ячейка в позиции р исключается из цепочек указателей и при необходимости может быть использована повторно.

Procedure Make(var x : pt); {Построение списка из пяти элементов}

var t,y:pt;

i: integer;

begin

new(x);

x^.prev:=nil;

for i:=1 to 5 do

begin

y:=x;

readln(y^.data);

if i<>5 then

begin

new(x);

y^.next:=x;

x^.prev:=y;

end

else

y^.next:=nil;

end;

Procedure Delete (p:pt);

Begin

If p^.previous <> nil then {Удаление ячейки, не являющейся первой}

p^.previous^.next:=p^.next;

If p^.next <> nil then {Удаление ячейки, не являющейся последней}

p^. next^. previous:=p^. previous;

End;

Рис. 1.5 Удаление элемента из дважды связного списка


Сейчас читают про: