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

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

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

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