Двунаправленный список с фиктивными элементами

Рисунок 3.3 – Двусвязный список c фиктивным элементом

На рисунке 3.2 показан список L, использующий фиктивный элемент nil[L] (темно – серый прямоугольник). Вместо head[L] используем next[nil[L]]. (a) Пустой список. (б) Список, у которого элемент с ключом 9 – голова, 1 - хвост). (в) Тот же список после процедуры List-Insert'(L,x), если key[x] = 25. (г) После удаления элемента с ключом 1. Новый хвост имеет ключ 4.

Если забыть об особых ситуациях на концах списка, процедуру List-Delete можно записать совсем просто:

Листинг 3.8 – Упрощенная процедура удаления элемента из списка

Такие упрощения станут «законными», если добавить к списку L фиктивный элемент nil[L], который будет иметь поля next и prev наравне с прочими эле­ментами списка. Этот элемент (называемый по-английски sentinel, что означает «часовой») не позволит выйти за пределы списка. Указатель на него играет роль значения NIL. Замкнём список в кольцо: в поля next[nil[L]] и prev[nil[L]] запишем указатели на голову и хвост списка соответственно, а в поля prev у головы списка и next у хвоста списка занесём указатели на nil[L] (рис. 3.2). При этом next[nil[L]] – указатель на голову списка, так что атрибут head[L] становится лишним. Пустой список L теперь будет кольцом, в котором nil[L] – единственный элемент.

В процедуре List-Search нужно лишь заменить NIL на nil[L] и head[L] на next[nil[L]]:

Листинг 3.9 – Процедура поиска в списке с фиктивным элементом

Для удаления элемента применяется процедура List-Delete, приведенная выше. Наконец, добавлять элемент к списку можно так:

Листинг 3.10 – Процедура добавления в список с фиктивным элементом

Пример работы процедур List-Insert и List-Delete показан на рис.3.2. Использование фиктивных элементов едва ли может улучшить асимптотику времени работы алгоритма, но упрощает программу. Иногда (если использование фиктивных элементов позволяет сократить фрагмент кода, находящийся глубоко внутри цикла), можно ускорить исполнение программы в несколько раз;

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