Почему именно нам нужна структура данных «Круговой связанный список» (поодиночке или вдвойне)?

Question

Почему именно нам нужна структура данных «Круговой связанный список» (в одиночку или в два раза)?

Какую проблему она решает, что очевидно при использовании простых связанных списков (в одиночку или в два раза)?

Answer 1

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

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

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

Answer 2

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

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

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

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

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

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

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

Answer 3

Приложения

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

Answer 4

Что-то, что я нашел в Google.

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

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

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

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

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

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

Answer 10

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