Шрифт:
Двухсвязные списки
После достаточно подробных исследований односвязных списков можно переходить к рассмотрению двухсвязных списков. Как и в случае с односвязными списками, здесь имеется набор связанных между собой узлов, но помимо ссылки на следующий узел существует ссылка и на предыдущий узел:
type
PSimpleNode = ^TSimpleNode;
TSimpleNode = record
Next : PSimpleNode;
Prior : PSimpleNode;
Data : SomeDataType;
end;
Таким образом, двухсвязный список позволяет двигаться по узлам не только вперед, по ссылкам Next, но и назад, по ссылкам Prior. Схематично двухсвязный список показан на рис. 3.4.
Рисунок 3.4. Двухсвязный список
Вставка и удаление элементов в двухсвязном списке
Каким образом вставлять новый узел в двухсвязный список? В односвязном списке для этого нужно было разорвать одну ссылку и вставить две новых, а для двухсвязного списка потребуется разорвать две ссылки и вставить четыре новых. Причем вставку можно выполнять как перед, так и после определенного элемента, поскольку указатель Prior позволяет проходить список в обратном направлении. Фактически операцию "вставить перед" можно запрограммировать как "перейти к предыдущему узлу и вставить после". Поэтому в главе мы рассмотрим только операцию "вставить после".
Ссылка Next нового узла устанавливается на узел, расположенный после заданного узла, а ссылка Next заданного узла устанавливается на новый узел. Для установки обратных ссылок ссылка Prior нового узла устанавливается на заданный узел, а ссылка Prior узла, следующего за новым, устанавливается на новый узел. В коде это выглядит следующим образом:
var
GivenNode, NewNode : PSimpleNode;
begin
• • •
New(NewNode);
.. задать значение поля Data ..
NewNode^.Next := GivenNode^.Next;
GivenNode^.Next := NewNode;
NewNode^.Prior := GivenNode;
NewNode^.Next^.Prior := NewNode;
В случае с удалением проще всего удалить узел, находящийся после заданного узла. Необходимо установить ссылку Next заданного узла на узел, находящийся после удаляемого, а ссылку Prior узла, находящегося после удаляемого, на заданный узел.
Рисунок 3.5. Вставка нового узла в двухсвязный список
После этих операций удаляемый узел исключен из списка, и его можно удалить. В коде это выглядит следующим образом:
var
GivenNode, NodeToGo : PSimpleNode;
begin
• • •
NodeToGo := GivenNode^.Next;
GivenNode^.Next := NodeToGo^.Next;
NodeToGo^.Next^.Prior := GivenNode;
Dispose(NodeToGo);
Как и для односвязных списков, здесь для обеих операций существуют специальные случаи: вставка перед первым элементом списка (т.е. новый элемент становиться первым) и удаление первого элемента списка (т.е. первым становится другой элемент). Поскольку в наших рассуждениях первый элемент считается определяющим узлом всего списка, код для этих случаев потребуется написать отдельно.
Рисунок 3.6. Удаление узла в двухсвязном списке
Вставка:
var
FirstNode, NewNode : PSimpleNode;
begin
• • •
New(NewNode);
.. задать значение поля Data..
NewNode^.Next := FirstNode;
NewNode^.Prior := nil;
FirstNode^.Prior := NewNode;
FirstNode := NewNode;
Удаление:
var
FirstNode, NodeToGo : PSimpleNode;
begin
• • •
NodeToGo := FirstNode;
FirstNode := NodeToGo^.Next;
FirstNode^.Prior := nil;
Dispose(NodeToGo);
Использование начального и конечного узлов
Для односвязного списка было показано, что наличие начального узла существенно упрощало операции вставки и удаления. Соответствующий случай для двухсвязного списка - наличие двух фиктивных узлов: начального и конечного. Они позволяют очень легко выполнять прохождение списка от первого узла к последнему, равно как от последнего к первому. Специальные случаи при этом исключаются.
Использование диспетчера узлов
Как и для односвязного списка, данные в списке удобно хранить в виде указателей. Это позволяет написать общий класс двухсвязного списка. В двухсвязном списке в каждом узле будет находиться прямой указатель, обратный указатель и указатель на данные. Общий размер узла составит 12 байт (т.е. 3*sizeof(pointer)). Все узлы одинаковы, таким образом, можно реализовать диспетчер узлов и для двухсвязного списка.