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

使用它们的两个原因:

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

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

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

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

它 能够 可以使用链表实现,但是会不断地添加和删除列表,而不是替换常量(后者更便宜)。

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

应用

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

我从谷歌找到的东西。

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

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

循环链表可以有效地用于创建队列(FIFO)或deque(从前面和后面高效地插入和删除)。看到了吗 http://en.wikipedia.org/wiki/Linked_list#Circularly-linked_vs._linearly-linked

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

循环链表(单或双)对于需要平等访问每个节点的应用程序非常有用 和 名单可能会增加。如果列表的大小是固定的,则使用循环队列的效率(速度和内存)要高得多。

追加 预支 向前移动一次, 弹回 弹出式前端 . 通过将两端连接在一起,就可以得到一个双端列表,而只需实现单端列表的操作。

在实际应用中:当您在系统上打开多个应用程序时,这些应用程序的内存以循环方式保存,如果您连续按win+tab/alt+tab切换应用程序,您可以观察到这一点。 同样在多人棋盘游戏中,每个玩家被分配到链表中的节点,并执行轮换