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)?
通过简单的链接列表（单独或双重）可以解决哪些问题？
8 个解决方案
#1
37
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) {
CircularList start = c;
do {
operateOnNode(c);
c = c->next;
} while(c != start);
}
#2
19
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.
例如，Monopoly板上的方块可以用循环链表表示，以映射到它们的固有结构。
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 could be 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).
它可以用链表实现，但是列表会有不断的添加和删除，而不是替换常量（更便宜）。
#3
10
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）循环链表是循环调度算法的基本思想。
#4
8
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.
单链接循环列表是链表，其中列表中的最后一个节点指向列表中的第一个节点。循环列表不包含NULL指针。
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.
在分时环境中，操作系统必须维护当前用户的列表，并且必须允许每个用户一次使用一小部分CPU时间，一个用户。操作系统将选择一个用户，让他/她使用少量的CPU时间，然后转到下一个用户等。
For this application, there should be no NULL pointers unless there is absolutely no one requesting CPU time.
对于这个应用程序，应该没有NULL指针，除非绝对没有人请求CPU时间。
#5
4
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
#6
1
A good example of an application where circular linked list should be used is a timesharing problem solved by the operating system.
应该使用循环链表的应用程序的一个很好的例子是操作系统解决的分时问题。
#7
0
A circular list is simpler than a normal doubly-linked list. Append is just prepend and shift forward once, Pop back is 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.
循环列表比普通的双向链表更简单。追加只是前置并向前移动一次，后退只是向后移动一次并弹出前方。通过将两端绑在一起，您可以得到一个双端列表，仅用于实现单端列表操作的成本。
#8
0
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.
我们可以在资源池中使用循环链表。如果许多用户想要使用共享资源，我们可以使用循环链接列表分配该资源。
#1
37
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) {
CircularList start = c;
do {
operateOnNode(c);
c = c->next;
} while(c != start);
}
#2
19
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.
例如，Monopoly板上的方块可以用循环链表表示，以映射到它们的固有结构。
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 could be 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).
它可以用链表实现，但是列表会有不断的添加和删除，而不是替换常量（更便宜）。
#3
10
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）循环链表是循环调度算法的基本思想。
#4
8
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.
单链接循环列表是链表，其中列表中的最后一个节点指向列表中的第一个节点。循环列表不包含NULL指针。
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.
在分时环境中，操作系统必须维护当前用户的列表，并且必须允许每个用户一次使用一小部分CPU时间，一个用户。操作系统将选择一个用户，让他/她使用少量的CPU时间，然后转到下一个用户等。
For this application, there should be no NULL pointers unless there is absolutely no one requesting CPU time.
对于这个应用程序，应该没有NULL指针，除非绝对没有人请求CPU时间。
#5
4
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
#6
1
A good example of an application where circular linked list should be used is a timesharing problem solved by the operating system.
应该使用循环链表的应用程序的一个很好的例子是操作系统解决的分时问题。
#7
0
A circular list is simpler than a normal doubly-linked list. Append is just prepend and shift forward once, Pop back is 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.
循环列表比普通的双向链表更简单。追加只是前置并向前移动一次，后退只是向后移动一次并弹出前方。通过将两端绑在一起，您可以得到一个双端列表，仅用于实现单端列表操作的成本。
#8
0
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.
我们可以在资源池中使用循环链表。如果许多用户想要使用共享资源，我们可以使用循环链接列表分配该资源。