Вставка и удаление элементов в двухсвязном списке
Вставка и удаление элементов в двухсвязном списке
Каким образом вставлять новый узел в двухсвязный список? В односвязном списке для этого нужно было разорвать одну ссылку и вставить две новых, а для двухсвязного списка потребуется разорвать две ссылки и вставить четыре новых. Причем вставку можно выполнять как перед, так и после определенного элемента, поскольку указатель 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);
Использование начального и конечного узлов
Для односвязного списка было показано, что наличие начального узла существенно упрощало операции вставки и удаления. Соответствующий случай для двухсвязного списка - наличие двух фиктивных узлов: начального и конечного. Они позволяют очень легко выполнять прохождение списка от первого узла к последнему, равно как от последнего к первому. Специальные случаи при этом исключаются.