Why exactly do we need a "Circular Linked List" (singly or doubly) data structure?

Question

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)?

Answer 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); } 

Answer 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).