55

为什么我们需要一个“循环链表”（单或双）数据结构？

它解决了哪些简单的链表（单链表或双链表）显而易见的问题？

4

10 回答 10

51

一个简单的例子是跟踪在多人棋盘游戏中轮到谁了。将所有玩家放在一个循环链表中。轮到一名玩家后，前进到列表中的下一位玩家。这将导致程序在玩家之间无限循环。

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

void traverse(CircularList *c) {
  if (is_empty(c)) {
    return;
  }
  CircularList start = c;
  do {
    operateOnNode(c);
    c = c->next;
  } while(c != start);
}
于 2010-08-28T16:04:37.297 回答
26

使用它们的两个原因：

1）一些问题域本质上是循环的。

例如，大富翁棋盘上的方块可以用循环链表表示，以映射到它们的固有结构。

2）为了提高效率，可以将一些解决方案映射到循环链表。

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

这可以在循环缓冲区中表示，而无需不断地分配和释放内存，因为插槽可以在播放后重新使用。

它可以用链表来实现，但是会不断地添加和删除列表，而不是替换常量（更便宜）。

于 2010-08-28T07:06:36.463 回答
13

我从谷歌找到的东西。

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

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

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

对于此应用程序，除非绝对没有人请求 CPU 时间，否则不应有 NULL 指针。

于 2010-08-28T08:27:51.357 回答
13

应用

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

于 2012-08-09T17:20:32.910 回答
6

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

于 2010-08-28T06:54:48.267 回答
1

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

于 2015-12-30T20:42:05.333 回答
1

循环链表广泛用于需要重复任务的应用程序或分时应用程序中。循环队列可以跟踪已经执行和必须执行的任务，一旦特定任务完成就跳转到下一个任务，当整组任务完成后再次跳转到第一个任务完成剩余的工作。实际使用中：当您在系统上打开多个应用程序时，这些应用程序的内存以循环方式保存，如果您连续按win+tab/alt+tab切换应用程序，您可以观察到这一点。同样在多人棋盘游戏中，每个玩家都被分配到链表中的节点并执行轮换

于 2018-12-14T20:46:59.570 回答
1

循环链表（单链表或双链表）对于需要平等访问每个节点并且链表可以增长的应用程序很有用。如果列表的大小固定，则使用循环队列更有效（速度和内存）。

于 2019-04-02T17:50:01.577 回答
0

循环列表比普通的双向链表更简单。Append只是前置并向前移动一次，Pop back只是向后移动一次并弹出 front。通过将两端捆绑在一起，您将获得一个双端列表，其成本仅为实现单端列表的操作。

于 2011-11-10T16:25:26.507 回答
0

我们可以在资源池中使用循环链表。如果很多用户想要使用一个共享资源，我们可以使用循环链表来分配该资源。

于 2014-11-01T05:41:46.957 回答