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



             

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


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

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

Циклический список

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

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

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

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

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

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




Содержание  Назад  Вперед