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