C语言 为什么我们需要“循环链表”（单个或双重）数据结构？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3589772/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Why exactly do we need a "Circular Linked List" (singly or doubly) data structure?
提问by user366312
Why exactly do we need a "Circular Linked List" (singly or doubly) data structure?
为什么我们需要“循环链表”（单个或双重）数据结构？
What problem does it solve that is evident with simple Linked Lists (singly or doubly)?
它解决了什么问题，这对于简单的链表（单链表或双链表）是显而易见的？
采纳答案by Oddthinking
Two reasons to use them:
使用它们的两个原因：
1) Some problem domains are inherently circular.
1) 一些问题域本质上是循环的。
For example, the squares on a Monopoly board can be represented in a circularly linked list, to map to their inherent structure.
例如，大富翁板上的方块可以用循环链表表示，以映射到它们的固有结构。
2) Some solutions can be mapped to a circularly linked list for efficiency.
2）一些解决方案可以映射到循环链表以提高效率。
For example, a jitter buffer is a type of buffer that takes numbered packets from a network and places them in order, so that (for example) a video or audio player can play them in order. Packets that are too slow (laggy) are discarded.
例如，抖动缓冲区是一种缓冲区，它从网络中获取编号的数据包并将它们按顺序放置，以便（例如）视频或音频播放器可以按顺序播放它们。太慢（滞后）的数据包将被丢弃。
This can be represented in a circular buffer, without needing to constantly allocate and deallocate memory, as slots can be re-used once they have been played.
这可以用循环缓冲区表示，无需不断分配和释放内存，因为插槽可以在播放后重新使用。
It couldbe implemented with a linked-list, but there would be constant additions and deletions to the list, rather than replacement to the constants (which are cheaper).
它可以用链表来实现，但会不断地添加和删除列表，而不是替换常量（更便宜）。
回答by Andrew Cone
A simple example is keeping track of whose turn it is in a multi-player board game. Put all the players in a circular linked list. After a player takes his turn, advance to the next player in the list. This will cause the program to cycle indefinitely among the players.
一个简单的例子是在多人棋盘游戏中跟踪轮到谁。将所有玩家放在一个循环链表中。在玩家轮到他之后，前进到列表中的下一个玩家。这将导致程序在玩家之间无限循环。
To traverse a circular linked list, store a pointer to the first element you see. When you see that element again, you have traversed the entire list.
要遍历循环链表，请存储指向您看到的第一个元素的指针。当您再次看到该元素时，您已经遍历了整个列表。
void traverse(CircularList *c) {
if (is_empty(c)) {
return;
}
CircularList start = c;
do {
operateOnNode(c);
c = c->next;
} while(c != start);
}
回答by Sarin Vadakkey Thayyil
Applications
应用
1) We can use circular linked list any application where the entries appear in a rotating manner.
2) Circular linked list is the basic idea of round robin scheduling algorithm.
1) 我们可以在任何条目以轮换方式出现的应用程序中使用循环链表。
2）循环链表是循环调度算法的基本思想。
回答by Praveen S
Something i found from google.
我从谷歌找到的东西。
A singly linked circular list is a linked list where the last node in thelist points to the first node in the list. A circular list does not contain NULL pointers.
A good example of an application where circular linked list should be used is a timesharing problem solved by the operating system.
In a timesharing environment, the operating system must maintain a list of present users and must alternately allow each user to use a small slice of CPU time, one user at a time. The operating system will pick a user, let him/her use a small amount of CPU time and then move on to the next user, etc.
For this application, there should be no NULL pointers unless there is absolutely no one requesting CPU time.
单向循环列表是一个链表，其中列表中的最后一个节点指向列表中的第一个节点。循环列表不包含 NULL 指针。
应该使用循环链表的应用程序的一个很好的例子是操作系统解决的分时问题。
在分时环境中，操作系统必须维护当前用户的列表，并且必须交替地允许每个用户使用一小部分 CPU 时间，一次一个用户。操作系统会选择一个用户，让他/她使用少量的 CPU 时间，然后转移到下一个用户，等等。
对于此应用程序，除非绝对没有人请求 CPU 时间，否则不应有 NULL 指针。
回答by amit
A circular linked list can be effectively used to create a queue (FIFO) or a deque (efficient insert and remove from front and back). See http://en.wikipedia.org/wiki/Linked_list#Circularly-linked_vs._linearly-linked
循环链表可以有效地用于创建队列（FIFO）或双端队列（高效的前后插入和删除）。见http://en.wikipedia.org/wiki/Linked_list#Circularly-linked_vs._linearly-linked
回答by Rahul Singal
A good example of an application where circular linked list should be used is a timesharing problem solved by the operating system.
应该使用循环链表的应用程序的一个很好的例子是操作系统解决的分时问题。
回答by wolf_flow
Circular linked lists are widely used in applications where tasks are to be repeated or in time sharing applications. Circular queue can keep a track of tasks which have been performed and which has to be performed,once the specific task is done it jumps to next one and when whole set of task is conpleted it again jumps to first task to complete the remaining job. In practical use : when you open multiple applications on your system the memory of those applications are saved in a circular fashion, you can observe this if u continuously press win+tab/alt+tab for switching applications. Also in multiplayer board games ,each player are assigned to node in the linked list and the rotation is performed
循环链表广泛用于需要重复任务的应用程序或分时应用程序。循环队列可以跟踪已经执行和必须执行的任务，一旦特定任务完成，它就会跳转到下一个任务，当整个任务集完成时，它再次跳转到第一个任务以完成剩余的工作。在实际使用中：当您在系统上打开多个应用程序时，这些应用程序的内存以循环方式保存，如果您连续按 win+tab/alt+tab 切换应用程序，您可以观察到这一点。同样在多人棋盘游戏中，每个玩家都被分配到链表中的节点并进行轮换。
回答by yoonghm
Circular linked lists (singly or doubly) are useful for applications that need to visit each node equally andthe lists could grow. If the size of the list if fixed, it is much more efficient (speed and memory) to use circular queue.
循环链表（单链表或双链表）对于需要平等访问每个节点并且链表可以增长的应用程序非常有用。如果列表的大小固定，则使用循环队列效率更高（速度和内存）。
回答by Nitish Goyal
We can use circularly linked list in resource pooling. If many users want to use a shared resource, we can allocate that resource using circularly linked list.
我们可以在资源池中使用循环链表。如果很多用户想要使用一个共享资源，我们可以使用循环链表来分配该资源。
回答by u0b34a0f6ae
A circular list is simpler than a normal doubly-linked list. Appendis just prependand shift forward once, Pop backis just shift back once and pop front. By tying the two ends together, you get a double-ended list for the cost of just implementing the operations of a one-ended list.
循环列表比普通的双向链表简单。Append只是prepend并向前移动一次，Pop back只是向后移动一次并pop front。通过将两端连接在一起，您将获得一个双端列表，其成本仅是实现单端列表的操作。
