为什么我们需要一个"循环链接列表"(单一或双重)数据结构？

Question

为什么我们需要一个"循环链接列表"(单一或双重)数据结构？

通过简单的链接列表(单独或双重)可以解决哪些问题？

Answer 1

一个简单的例子就是跟踪多人棋盘游戏的转折点.将所有玩家放入循环链表中.在玩家轮到他之后,前进到列表中的下一个玩家.这将导致程序在玩家之间无限循环.

要遍历循环链表,请存储指向您看到的第一个元素的指针.当您再次看到该元素时,您已遍历整个列表.

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

Answer 2

使用它们的两个原因:

1)一些问题域本质上是循环的.

例如,Monopoly板上的方块可以用循环链表表示,以映射到它们的固有结构.

2)为了提高效率,可以将一些解决方案映射到循环链表.

例如,抖动缓冲区是一种缓冲区,它从网络中获取编号的数据包并按顺序放置它们,以便(例如)视频或音频播放器可以按顺序播放它们.丢弃太慢(滞后)的数据包.

这可以在循环缓冲区中表示,而不需要经常分配和释放内存,因为一旦它们被播放就可以重新使用.

它可以用链表实现,但是列表会有不断的添加和删除,而不是替换常量(更便宜).

Answer 3

应用

1)我们可以使用循环链表任何条目以旋转方式出现的应用程序.
2)循环链表是循环调度算法的基本思想.

Answer 4

我从谷歌找到的东西.

单链接循环列表是链表,其中列表中的最后一个节点指向列表中的第一个节点.循环列表不包含NULL指针.

应该使用循环链表的应用程序的一个很好的例子是操作系统解决的分时问题.

在分时环境中,操作系统必须维护当前用户的列表,并且必须允许每个用户一次使用一小部分CPU时间,一个用户.操作系统将选择一个用户,让他/她使用少量的CPU时间,然后转到下一个用户等.

对于这个应用程序,应该没有NULL指针,除非绝对没有人请求CPU时间.

Answer 5

循环链表可以有效地用于创建队列(FIFO)或双端队列(高效插入和从前面和后面移除).见http://en.wikipedia.org/wiki/Linked_list#Circularly-linked_vs._linearly-linked