Главная » Ядро Linux » Кольцевые связанные списки

0

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

next                          next                         next

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

prev                 next      prev                  next      prev                 next

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

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

Перемещение по связанному списку

Перемещение   по  связанному  списку  выполняется  последовательно   (линейно). После  того как просмотрен  текущий  элемент,  выполнятся  разыменование его указателя next ,  что позволяет  обратиться  к следующему за ним элементу и т.д. Это самый простой  и  наиболее  подходящий  метод  перемещения   но  связанному  списку.  Если важна  возможность  произвольного  доступа к любому элементу контейнера,   то связанные  списки  не  используются.  Связанные  списки  используются,  когда  важна  возможность  динамического  добавления  и удаления  элементов,   а также  возможность последовательного  прохождения  по  всем элементам  списка.

Часто  первый элемент списка представлен с помощью специального указателя, который называется головным элементом или головой (head), что дает возможность быстро  и легко  обращаться к первому  элементу. В некольцевом связанном списке последний элемент отличается тем, что его указатель  равен значению NULL. В кольцевом связанном списке последний элемент отличается тем, что указывает на головной элемент. Таким  образом прохождение списка можно  выполнить линейно, начиная с первого  элемента и заканчивая последним. В двухсвязном списке прохождение можно также выполнить и в противоположном направлении, начиная с последнего и заканчивая первым  элементом. Конечно, если задан определенный элемент списка, то можно  перейти по списку  вперед  и назад  на заданное количество элементов. При этом  нет необходимости проходить весь список.

Источник: Лав,  Роберт. Разработка ядра  Linux, 2-е  издание. : Пер.  с англ.  — М.  : ООО  «И.Д.  Вильяме» 2006. — 448 с. : ил. — Парал. тит. англ.

По теме:

  • Комментарии