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

Для односвязного списка существует только один вариант вставки - после заданного элемента списка. Нужно установить так, чтобы указатель Next нашего нового узла указывал на узел после заданного, а указатель Next заданного узла -на наш новый узел. В коде это выглядит следующим образом:

var
GivenNode, NewNode : PSimpleNode;
begin
• • •
New(NewNode);
.. задать значение поля Data.. NewNode Л. Next : - GivenNode A. Next ; GivenNode A. Next : = NewNode;

Аналогично, для удаления простейшим вариантом является удаление элемента, находящегося после заданного узла. В этом случае мы устанавливаем, чтобы ука-

затель Next заданного узла указывал на узел, расположенный после удаляемого. После этого удаляемый узел уже выделен из списка и может быть освобожден. В коде это выглядит следующим образом:

var
GivenNode, NodeToGo : PSimpleNode;
begin
• • •
NodeToGo : = GivenNodeA.Next;
GivenNodeA.Next : = NodeToGoA.Next;
Dispose(NodeToGo);
Удаление узла из односвязного списка

Рисунок 3.3. Удаление узла из односвязного списка

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

var
GivenNode, NewNode : PSimpleNode;
begin
• • •
New(NewNode);
. . задать значение поля Data.. NewNodeA.Next : = MyLinkedList;
MyLinkedLis t: = NewNode ;

а удаление будет выглядеть так: var GivenNode, NodeToGo : PSimpleNode; begin • • •

NodeToGo : = GivenNodeA.Next;
MyLinkedList: = NodeToGoA. Next;
Dispose(NodeToGo);

Обратите внимание, что код вставки элемента будет работать даже в случае, когда исходный список пуст, т.е. содержит nil, а код удаления элемента правильно установит содержимое связного списка в случае удаления из него последнего узла.

Создание односвязного списка || Оглавление || Прохождение связного списка


Фундаментальные алгоритмы и структуры данных в Delphi



Новости за месяц

  • Июль
    2020
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31