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

Голова списка

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

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

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

Циклический список обычно представлен в программе указателем на хвост (Tail), так как получить в этом случае указатель на начало не представляет труда. Для циклических списков становятся простыми операции сцепления и расщепления. Рис. 8 иллюстрирует операцию расщепления по узлу P. Пунктиром изображено изменение связей после операции.

Рис.8 Расщепление списка

На языке СИ это может быть записано следующим образом:

NODE *x;

x=P->Next;

P->Next=Tail->Next;

Tail->Next=x;

Нетрудно заметить, что операция выполняет обмен местами указателей P->Next и Tail->Next. Следовательно, повторное применение той же операции приведет к сцеплению списков. Операция работает как кнопочный выключатель.

Дата добавления: 2014-12-08