Вставка и удаление элементов в двухсвязном списке

Вставка и удаление элементов в двухсвязном списке

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

Использование начального и конечного узлов

Для односвязного списка было показано, что наличие начального узла существенно упрощало операции вставки и удаления. Соответствующий случай для двухсвязного списка - наличие двух фиктивных узлов: начального и конечного. Они позволяют очень легко выполнять прохождение списка от первого узла к последнему, равно как от последнего к первому. Специальные случаи при этом исключаются.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Вставка специальных элементов

Из книги автора

Вставка специальных элементов Возможности программы предусматривают вставку в контент веб-страницы специальных элементов – гиперссылок, изображений, фреймов и т. д. Необходимый для этого инструмент находится на вкладке


Удаление элементов АСЕ

Из книги автора

Удаление элементов АСЕ Функция DeleteAce удаляет АСЕ, определяемый с помощью индекса аналогично тому, как это делается в случае функции


Добавление и удаление элементов Web-страницы

Из книги автора

Добавление и удаление элементов Web-страницы А теперь — высший пилотаж Web-программирования! Программное добавление на Web-страницу новых элементов и программное же их удаление. Для этого применяют методы объекта DomHelper.Метод append добавляет новый элемент Web-страницы в


Добавление и удаление элементов Web-страницы

Из книги автора

Добавление и удаление элементов Web-страницы А теперь — высший пилотаж Web-программирования! Программное добавление на Web-страницу новых элементов и программное же их удаление. Для этого применяют методы объекта DomHelper.Метод append добавляет новый элемент Web-страницы в


Добавление и удаление элементов таблицы

Из книги автора

Добавление и удаление элементов таблицы При редактировании таблицы иногда бывает необходимо добавлять в нее дополнительные элементы – строки или столбцы. Для этого выделите такое количество строк или столбцов, какое нужно добавить. Затем перейдите на вкладку Работа с


8.1.14. Удаление из массива элементов равных nil

Из книги автора

8.1.14. Удаление из массива элементов равных nil Метод compact (и его вариант compact! для модификации на месте) удаляет из массива элементы равные nil, оставляя все остальные без изменения:a = [1, 2, nil, 3, nil, 4, 5]b = a.compact # [1, 2, 3, 4, 5]a.compact!    # а равно [1, 2, 3, 4,


8.1.15. Удаление заданных элементов из массива

Из книги автора

8.1.15. Удаление заданных элементов из массива В Ruby легко удалить элементы из массива - для этого даже существует много способов. Чтобы удалить элемент с известным индексом, достаточно вызвать метод delete_at:a = [10, 12, 14, 16, 18]a.delete_at(3) # Возвращает 16.# а равно [10, 12, 14, 18]a.delete_at(9) #


Динамическое добавление (и удаление) элементов управления

Из книги автора

Динамическое добавление (и удаление) элементов управления Но что делать, если нужно изменить содержимое Panel в среде выполнения? Соответствующий процесс должен показаться вам очень знакомым, если вы внимательно прочитали материал книги, посвященный работе с Windows Forms.


Вставка и удаление элементов в односвязном списке

Из книги автора

Вставка и удаление элементов в односвязном списке А каким образом можно вставить новый элемент в связный список? Или удалить? Оказывается, что для выполнения этих операций требуется выполнить небольшую работу с указателями.Для односвязного списка существует только


Удаление элементов из хеш-таблицы с линейным зондированием

Из книги автора

Удаление элементов из хеш-таблицы с линейным зондированием Прежде чем приступить к рассмотрению конкретного кода, рассмотрим удаление элементов из хеш-таблицы. Эта задача кажется достаточно простой: необходимо выполнить хеширование ключа элемента, который нужно


6.12.5. Удаление элементов map

Из книги автора

6.12.5. Удаление элементов map Существуют три формы функции-члена erase() для удаления элементов отображения. Для единственного элемента используется erase() с ключом или итератором в качестве аргумента, а для последовательности эта функция вызывается с двумя итераторами.


Удаление элементов Проводника

Из книги автора

Удаление элементов Проводника Существует возможность запрета отображения некоторых элементов Проводника. В данном разделе книги мы подробнее познакомимся с этой возможностью.Удаление меню ФайлС помощью несложной операции можно удалить меню Файл из главного меню как


Расстановка приоритетов в списке дел

Из книги автора

Расстановка приоритетов в списке дел Итак, вы сидите за рабочим столом, и перед вами список сегодняшних дел. Десятки пунктов. Как вы определите, с чего начать?Этот раздел посвящен расстановке приоритетов в этом списке. В разных ситуациях приходится использовать разные