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

Question

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

它解决了简单链表(单链表或双链表)明显的什么问题？

Answer 1

使用它们的两个原因：

1)一些问题域本质上是圆形的。

例如，垄断板上的方块可以用循环链表表示，以映射到它们的固有结构。

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

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

这可以在循环缓冲区中表示，而不需要不断地分配和释放内存，因为一旦播放了插槽，就可以重用它们。

它可以用链表来实现，但是会不断地对链表进行添加和删除，而不是替换常量(更便宜)。

Answer 2

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

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

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

Answer 3

我在谷歌上找到的东西。

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

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

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

对于这个应用程序，不应该有空指针，除非绝对没有人请求CPU时间。