Комбинаторные алгоритмы для программистов

         

Разновидности связанных списков


Тривиальной модификацией связанного списка, изображенного на рис 3.2, будет следующее несколько более гибкое представление последовательности: если

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


Рис. 3.5.  Циклический список

Еще большая гибкость достигается, если использовать дважды связанный список, когда каждый элемент

последовательности вместо одного имеет два связанных с ним указателя. Как показано на рис. 3.6, они указывают на элементы
и
. В таком списке для любого элемента имеется мгновенный прямой доступ к предыдущему и последующему элементам, в связи с чем облегчаются такие операции, как включение нового элемента перед
и исключение элемента

без предварительного знания его предшественника. Если есть необходимость, дважды связанный список очевидным образом можно сделать циклическим.


Рис. 3.6.  Дважды связанный список



Содержание раздела