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

Solution 1

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

Solution 2

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 3

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.

Solution 4

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.

Solution 5

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

View more solutions

Comments

[Swapnil]

I read the above comment as "Why exactly do we need a circular linked list? Because the goal of SO is to be the correct first place...." Then I read the earlier "-1" comment :D

[Grant Peters]

A particle system I wrote for a game uses a circular list for the particles. If we run out of unused particles (limited for performance and memory reasons), then we just overwrite the oldest ones (which will just be at the "start" of the loop, as we write to the back).

[Oddthinking]

Sorry, I can't provide web-links for my claims. Call it original research. :-) The Monopoly board is an invented example to illustrate the idea. I have never seen the code of a Monopoly implementation. The jitter buffer example is based on a few examples of code that I have developed and/or worked on.

[u0b34a0f6ae]

A general traversal also needs if (!is_empty(c)) { ... } around the whole do .. while loop.

[day]

Can't these problems be solved with just a normal linked list together with a loop?

[omerfarukdogan]

Is it too hard to use if(!c) c=head; in a single linked list instead of implementing this?

[Pithikos]

In your words a circular list is a single list with both ends connected. OK, but how is that any good?

[Pithikos]

@day sure. With a circular list though, you trade off algorithm complexity for (a rather small) structure complexity. Having a loop would mean having at least an extra check while with a circular list your structure is inherently solving this for you.

[Oddthinking]

@omerfarukdogan (late response!) That is an extra check that needs to be applied at every node. (Remember the start might be halfway through the linked list.) It is more efficient to get rid of the check by making the list circular, and remove the need to test before every navigation.