Защо точно се нуждаем от структура от данни с кръгъл свързан списък (единично или двойно)?

Две причини да ги използвате:

1) Някои проблемни области по своята същност са кръгови.

Например, квадратите на дъска за монополи могат да бъдат представени в кръгово свързан списък, за да се съпоставят с присъщата им структура.

2) Някои решения могат да бъдат съпоставени към кръгово свързан списък за ефективност.

Например буферът за трептене е вид буфер, който взема номерирани пакети от мрежа и ги поставя в ред, така че (например) видео или аудио плейър да може да ги възпроизвежда в ред. Пакетите, които са твърде бавни (забавени), се отхвърлят.

Това може да бъде представено в кръгъл буфер, без да е необходимо постоянно да се разпределя и освобождава памет, тъй като слотовете могат да се използват повторно, след като са били изиграни.

Той може да бъде приложен със свързан списък, но ще има постоянни добавяния и изтривания към списъка, вместо замяна на константите (които са по-евтини).

Един прост пример е да следите кой е редът в настолна игра за много играчи. Поставете всички играчи в кръгов свързан списък. След като играч вземе своя ред, преминете към следващия играч в списъка. Това ще накара програмата да се върти безкрайно между играчите.

За да преминете през кръгъл свързан списък, запазете указател към първия елемент, който видите. Когато видите този елемент отново, вие сте преминали през целия списък.

void traverse(CircularList *c) {
  if (is_empty(c)) {
    return;
  }
  CircularList start = c;
  do {
    operateOnNode(c);
    c = c->next;
  } while(c != start);
}

Приложения

1) Можем да използваме кръгов свързан списък всяко приложение, където записите се появяват по редуващ се начин.
2) Кръговият свързан списък е основната идея на алгоритъма за кръгово планиране.

Нещо, което намерих от гугъл.

Единично свързан кръгов списък е свързан списък, където последният възел в списъка сочи към първия възел в списъка. Кръговият списък не съдържа NULL указатели.

Добър пример за приложение, където трябва да се използва кръгов свързан списък, е проблемът с споделянето на времето, разрешен от операционната система.

В среда със споделяне на времето операционната система трябва да поддържа списък с настоящи потребители и трябва последователно да позволява на всеки потребител да използва малък отрязък от процесорното време, един потребител наведнъж. Операционната система ще избере потребител, ще му позволи да използва малко време на процесора и след това ще премине към следващия потребител и т.н.

За това приложение не трябва да има NULL указатели, освен ако няма абсолютно никой, който да поиска процесорно време.

Кръговият свързан списък може ефективно да се използва за създаване на опашка (FIFO) или deque (ефективно вмъкване и премахване отпред и отзад). Вижте http://en.wikipedia.org/wiki/Linked_list#Circularly-linked_vs._linearly-linked

Добър пример за приложение, където трябва да се използва кръгов свързан списък, е проблемът с споделянето на времето, разрешен от операционната система.

Кръговите свързани списъци (единично или двойно) са полезни за приложения, които трябва да посещават всеки възел еднакво и списъците могат да се разрастват. Ако размерът на списъка е фиксиран, е много по-ефективно (скорост и памет) да се използва кръгова опашка.

Кръговият списък е по-прост от нормален двойно свързан списък. Добавяне е само предваряване и преместване напред веднъж, Изскачане назад е само преместване назад веднъж и изскачане отпред. Като свържете двата края заедно, вие получавате списък с двоен край на цената на просто прилагане на операциите на списък с един край.

Можем да използваме кръгово свързан списък в обединяването на ресурси. Ако много потребители искат да използват споделен ресурс, можем да разпределим този ресурс с помощта на кръгово свързан списък.

Кръговите свързани списъци се използват широко в приложения, където задачите трябва да се повтарят или в приложения за споделяне на време. Циркулярната опашка може да следи задачите, които са били изпълнени и които трябва да бъдат изпълнени, след като конкретната задача е изпълнена, тя преминава към следващата и когато целият набор от задачи е завършен, отново преминава към първата задача, за да завърши оставащата задача. При практическа употреба: когато отворите множество приложения на вашата система, паметта на тези приложения се записва в кръг, можете да наблюдавате това, ако натискате непрекъснато win+tab/alt+tab за превключване на приложения. Също така в настолните игри за много играчи всеки играч се присвоява на възел в свързания списък и ротацията се извършва