Почему именно нам нужна структура данных "Circular Linked List" (по отдельности или вдвое)?

Ответ 1

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

Чтобы пересечь круговой связанный список, сохраните указатель на первый элемент, который вы видите. Когда вы снова увидите этот элемент, вы пройдете весь список.

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

Ответ 2

Две причины для их использования:

1) Некоторые области проблем по своей сути являются круговыми.

Например, квадраты на плате монополии могут быть представлены в циклически связанном списке, чтобы отобразить их внутреннюю структуру.

2) Некоторые решения могут быть сопоставлены с круговым списком для эффективности.

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

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

Он может быть реализован с помощью связанного списка, но в списке будут постоянные добавления и удаления, а не замена констант (которые дешевле).

Ответ 3

Приложения

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

Ответ 4

Что-то я нашел из google.

Односвязный круговой список - это связанный список, в котором последний node в списке указывает на первый node в списке. Циклический список не содержит указателей NULL.

Хорошим примером приложения, в котором должен использоваться круговой связанный список, является проблема с временным разделением, решаемая операционной системой.

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

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

Ответ 5

Круговой связанный список может эффективно использоваться для создания очереди (FIFO) или deque (эффективная вставка и удаление спереди и сзади). См. Http://en.wikipedia.org/wiki/Linked_list#Circularly-linked_vs._linearly-linked.

Ответ 6

Хорошим примером приложения, в котором должен использоваться круговой связанный список, является проблема с временным разделением, решаемая операционной системой.

Ответ 7

Круговой список проще, чем обычный двусвязный список. Append просто добавляется и сдвигается вперед один раз, Pop back - это просто сдвиг назад один раз и поп-фронт. Соединяя два конца вместе, вы получаете список с двойным концом за стоимость только выполнения операций в одноконтурном списке.

Ответ 8

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

Ответ 9

Круговые связанные списки широко используются в приложениях, где необходимо повторять задачи, или в приложениях с разделением времени. Круговая очередь может отслеживать задачи, которые были выполнены и которые должны быть выполнены, после выполнения определенной задачи она переходит к следующей, а когда весь набор задач завершается, она снова переходит к первой задаче, чтобы завершить оставшуюся работу. На практике: когда вы открываете несколько приложений в своей системе, память этих приложений сохраняется по кругу, вы можете наблюдать это, если постоянно нажимаете win + tab/alt + tab для переключения приложений. Также в многопользовательских настольных играх каждому игроку назначается узел в связанном списке, и выполняется ротация.

Ответ 10

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