Рнс. 3.3

Простейшие операции, производимые над односвязными списками

1) Вставка в начало односвязного списка. Надо вставить в начало односвязного списка элемент с информационным полем D. Для этого необходимо сгенери­ровать пустой элемент (P=GetNode). Информационному по­лю этого элемента присвоить значение D (INFO(P)=D), зна­чению указателя на этот элемент присвоить значение указа­теля на начало списка (Ptr(P) = Lst), значению указателя на­чата списка присвоить значение указателя Р (Lst = Р).

Вставка в начало списка

P=GetNode

Info(P)=x

Ptr(P) = Lst

Lst = P

return

2) Удаление элемента из начала односвязного списка. Надо удалить первый элемент списка, но запомнить ин­формацию, содержащуюся в поле Info этого элемента. Для этого введем указатель Р, который будет указывать на уда­ляемый элемент (Р = Lst). В переменную X занесем значение информационного поля Info удаляемого элемента (X=Info(P)). Значению указателя на начало списка присвоим значение указателя следующего за удаляемым элемента (Lst = Ptr(P)). Удалим элемент (FreeNode(P)).

Удаление из начала списка

P = Lst

x=Info(P)

Lst = Ptr(P)

FreeNode(P)

return

Двусвязный список

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

Для устранения этого неудобства добавим в каждое зве­но списка еще одно поле, значением которого будет ссылка на предыдущее звено списка. Динамическая структура, со­стоящая из элементов такого типа, называется двунаправленным или двусвязным списком.

Двусвязный список характеризуется тем, что у любого элемента есть два указателя. Один указывает на предыдущий элемент (обратный), другой указывает на следующий элемент (прямой) (рис. 3.4).

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