Кольцевые связанные списки

Кольцевые связанные списки

Последний элемент связанного списка не имеет следующего за ним элемента, и значение указателя next последнего элемента обычно устанавливается равным специальному значению, обычно NULL, чтобы показать, что этот элемент списка является последним. в определенных случаях последний элемент списка не указывает на специальное значение, а указывает на первый элемент этого же списка. Такой список называется кольцевым связанным списком (circular linked list), поскольку связи образуют топологию кольца. Кольцевые связанные списки могут быть как односвязными, так и двухсвязными. В двухсвязных кольцевых списках указатель prev первого элемента указывает на последний элемент списка. На рис. А.3 и А.4 показаны соответственно односвязные и двухсвязные кольцевые списки.

Рис. A.3. Односвязный кольцевой список

Рис. А.4. Двухсвязный кольцевой список

Стандартной реализацией связанных списков в ядре Linux является двухсвязный кольцевой список. Такие связанные списки обеспечивают наибольшую гибкость работы.