Рубрики

Круговой связанный список | Комплект 1 (Введение и приложения)

Мы обсуждали односвязные и двусвязные списки в следующих постах.

Введение в связанный список и вставку
Введение и вставка двусвязных списков

Круговой связанный список — это связанный список, в котором все узлы соединены в круг. В конце нет NULL. Круговой связанный список может быть однократно круговым связанным списком или дважды круговым связанным списком.

Преимущества круговых связанных списков:
1) Любой узел может быть отправной точкой. Мы можем пройти весь список, начиная с любой точки. Нам просто нужно остановиться, когда первый посещенный узел снова посещается.

2) Полезно для реализации очереди. В отличие от этой реализации, нам не нужно поддерживать два указателя для передней и задней частей, если мы используем круговой связанный список. Мы можем поддерживать указатель на последний вставленный узел, и front всегда можно получить как следующий за последним.

3) Круговые списки полезны в приложениях для многократного обхода списка. Например, когда на ПК запущено несколько приложений, для операционной системы характерно помещать запущенные приложения в список, а затем циклически перебирать их, давая каждому из них отрезок времени для выполнения, а затем заставляя их ждать. в то время как процессор отдается другому приложению. Для операционной системы удобно использовать циклический список, так что, когда он достигает конца списка, он может переходить к началу списка.

4) Круглые двусвязные списки используются для реализации расширенных структур данных, таких как куча Фибоначчи .

Следующие сообщения:
Круговой связанный список | Набор 2 (Обход)
Круговой односвязный список | вставка

Пожалуйста, напишите комментарии, если вы обнаружите какую-либо ошибку в приведенном выше коде / алгоритме, или найдете другие способы решения той же проблемы.

Рекомендуемые посты:

Круговой связанный список | Комплект 1 (Введение и приложения)

0.00 (0%) 0 votes