Why exactly do we need a "Circular Linked List" (singly or doubly) data structure?
Solution 1:
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);
}
Solution 2:
Two reasons to use them:
1) Some problem domains are inherently circular.
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.
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).