Кольцевой односвязный список получается из обычного односвязного списка путем присваивания указателю последнего элемента списка значение указателя начала списка (рис 3.3).

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

Вставка в начало односвязного списка.

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

Алгоритм операции вставки в начало списка следующий:

P = GetNode

Info ( P )= x

Ptr ( P ) = Lst ‘( Lst уже не указывает на начало списка)’

Lst = P ‘(новое начало)’

return

                                   Рис. 3.3’

Удаление элемента из начала односвязного списка.

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

Алгоритм операции удаления из начала списка следующий:

P = Lst

x=Info(P)

Lst = Ptr(P)

FreeNode(P)

return

                                   Рис. 3.3’’

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

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

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

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

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

Кольцевой двусвязный список

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