Двусвязный список

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

type TInfo = integer;

PNode = ^TNode;

TNode = record

Info: TInfo;

Next, // указатель на следующий элемент

Pred: PNode; // указатель на предыдущий элемент

end;

Движение по такому списку может происходить в двух направлениях: от начала к концу — с использованием указателя Next, и от конца к началу, используя указатель Pred. Пример двусвязного списка показан на рис. 9.7.

Рис. 9.7. Двусвязный список

Очевидно, что значение поля Next последнего элемента и поля Pred первого элемента линейного двусвязного списка равны Nil.

Включение нового элемента в двусвязный список и удаление элемента происходит и проще, и сложнее, чем в односвязный. Проще — потому что элемент двусвязного списка содержит указатели и на следующий, и на предыдущий элементы, и нет нужды, как при вставке в односвязный список, либо обменивать информационные поля местами, либо тащить, при проходе по списку, дополнительный указатель на предыдущий элемент. Сложнее — потому что требуется переприсвоить и значения указателей Next, и значения указателей Pred. На рис. 9.8 показана вставка элемента в двусвязный список. Прежние значения указателей показаны светло-серым цветом.

Рис. 9.8. Вставка элемента в двусвязный список

Для того чтобы вставить в список новый элемент после элемента p (см. рис. 9.8), необходимы следующие действия:

new(q); // создание нового элемента

with q^ do begin

Info:=34;

Next:=p^.Next;

Pred:=p;

end;

p^.Next^.Pred:=q; // меняется значение поля Pred элемента со значением 44

p^.Next:=q;

Удаление элемента p из двусвязного списка показано на рис. 9.9.

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

Удаление производится следующими действиями:

p^.Pred^.Next:=p^.Next; // связать предыдущий элемент со следующим за p

p^.Next^.Pred:=p^.Pred; // связать следующий за p элемент с предыдущим

dispose(p) // удаление элемента