Двусвязный список
Лекция 2
Линейные односвязные списки, содержащие только один указатель — на следующий элемент, позволяют двигаться лишь в одном направлении — от начала списка к его концу. Можно построить список, каждый элемент которого содержит два указателя: на следующий элемент и на предыдущий. В этом случае описание типов и переменных будет таким:
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) // удаление элемента