9.1.3. Двусвязный список
Линейные односвязные списки, содержащие только один указатель — на следующий элемент, позволяют двигаться лишь в одном направлении — от начала списка к его концу. Можно построить список, каждый элемент которого содержит два указателя: на следующий элемент и на предыдущий. В этом случае описание типов и переменных будет таким:
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) // удаление элемента
9.1.4. Кольцевой список
Если последний элемент линейного списка связать с первым посредством указателя Next, то получится кольцевой односвязный список, как показано на рис. 9.10.
Рис. 9.10. Односвязный кольцевой список
Для создания двусвязного кольцевого списка необходимо связать последний элемент с первым как по указателю Next, так и по указателю Pred. Двусвязный кольцевой список показан на рис. 9.11.
Рис. 9.11. Двусвязный кольцевой список
Разумеется, на одном из элементов кольцевого списка должен стоять указатель, и этот элемент условно считается первым.
В качестве примера использования двусвязного кольцевого списка решим следующую задачу. Дети стали в круг, взявшись за руки. Начав отсчет от первого, каждый i-тый выходит из круга, а круг смыкается. Кто останется?
Первая часть задачи — создание списка. Процедура Insert2 вставляет элемент в двусвязный список.
Листинг 9.8. Процедура Insert2 вставляет элемент в двусвязный список
procedure Insert2(var r: PNode; e: TInfo);
// вставка элемента в двусвязный список
var t: PNode;
begin
if r=Nil then begin // список пуст, создание первого элемента
new(r);
with r^ do begin
Info:=e;
Next:=r; Pred:=r; // ссылки замыкаем на себя
end;
end
else begin
new(t);
with t^ do begin
Info:=e; Next:=r^.Next; Pred:=r;
end;
r^.Next^.Pred:=t; r^.Next:=t;
end
end;
Вызвав эту процедуру K раз, получим список, содержащий K элементов. Указатель списка стоит на первом включенном в список элементе.
Вторая часть задачи – удаление i-того элемента, считая от первого. Алгоритм прост: отсчитывается заданное количество элементов, требуемый элемент удаляется, указатель на список переносится на следующий за удаленным элемент. Когда в списке останется только один элемент, его поля Pred и Next будут указывать на него самого. Функция CountDel реализует этот алгоритм.
Листинг 9.9. Удаление элемента
function CountDel (var p: PNode; step: integer): PNode;
var r,t: PNode;
i : integer;
begin
r:=p;
repeat
for i:=1 to step do r:=r^.Next;
t:=r^.Pred; // этот элемент будем удалять
t^.Pred^.Next:=r; r^.Pred:=t^.Pred; // замыкаем круг
dispose(t)
until r=r^.Next;
Result:=r;
end;