Почему именно нам нужен «Круговой связанный список» (в одиночку или в два раза) данных структура?
Почему именно нам нужна структура данных «Круговой связанный список» (поодиночке или вдвойне)?
Какую проблему он решает? очевидно с простыми связанными списками (в одиночку или в два раза)?
3 ответа
Простым примером является отслеживание хода в многопользовательской настольной игре. Поместите всех игроков в круговой связанный список. После того, как игрок сделает свой ход, перейдите к следующему игроку в списке. Это заставит программу бесконечно переключаться между игроками.
Чтобы просмотреть круговой связанный список, сохраните указатель на первый элемент, который вы видите. Когда вы снова видите этот элемент, вы прошли весь список.
void traverse(CircularList *c) {
CircularList start = c;
do {
operateOnNode(c);
c = c->next;
} while(c != start);
}
Круговой связанный список можно эффективно использовать для создания очереди (FIFO) или дека (эффективная вставка и удаление спереди и сзади). См. http://en.wikipedia.org/wiki/Linked_list#Circularly-linked_vs._linearly-linked
Две причины для их использования:
1) Некоторые проблемные области по своей природе замкнуты.
Например, клетки на доске «Монополия» могут быть представлены в виде кругового списка, чтобы соответствовать их внутренней структуре.
2) Некоторые решения могут быть сопоставлены с циклически связанным списком для повышения эффективности.
Например, буфер дрожания — это тип буфера, который принимает пронумерованные пакеты из сети и размещает их по порядку, чтобы (например) видео- или аудиоплеер мог воспроизводить их по порядку. Пакеты, которые слишком медленные (отстающие), отбрасываются.
Это может быть представлено в циклическом буфере без необходимости постоянного выделения и освобождения памяти, поскольку слоты могут повторно использоваться после того, как они были воспроизведены.
Его можно реализовать с помощью связанного списка, но будут постоянные добавления и удаления в список, а не замена констант (которые дешевле).