Circular Queue and Circular Linked List

Question

I want to have a clear difference between circular queue and circular single linked list ?? Although on the outset,both look nearly same....

Answer 1

Circular queue or Circular Buffer: is a way of implementing a queue. For example, suppose you want to implement a queue using an array. You'd have your enqueue() and dequeue() methods.

Suppose the underlying array is of length 7, and the user enqueues five values, so the values in the underlying array look like this:

            head                   tail
position:  | 0 | 1  | 2 | 3 | 4  |   5  |   6  |
value:     | 3 | 12 | 5 | 4 | 71 | free | free |

Now the user wants to dequeue an element, removing value 3 from position 0. As the queue implementer, you'd have to figure out how to handle this. A basic solution would be to move all values down by one position so the underlying array now looks like this:

            head               tail
position:  | 0  | 1 | 2 | 3  | 4    |   5  |   6  |
value:     | 12 | 5 | 4 | 71 | free | free | free |

but that may require unnecessarily copying a lot of values every time you dequeue anything! One way to avoid that is to say that your head is now at position 1 instead of 0,

                   head               tail
position:  |   0  | 1  | 2 | 3 | 4  |   5  |   6  |
value:     | free | 12 | 5 | 4 | 71 | free | free | 

so now every time you add a new element you'll just add it to the tail (and increment the tail position), and if you remove an element, you'll just move the head. This way you don't have to do any unnecessary copying.

Once the tail reaches the end of the array it'll start wrapping over to the beginning of the array -- i.e. the queue will move in "circle" over the underlying array. For example, after a few more enqueues and dequeues, the underlying array would look like this:

                  tail                head
position:  | 0  |   1  |   2  |   3  | 4  | 5  | 6 |
value:     | 91 | free | free | free | 71 | 22 | 8 | 

The tail now wrapped around to the beginning of the array.

Circular linked list: a linked list where the head points to the tail. It's a general-purpose circular structure. It can be used to implement a circular queue/buffer, or it may be used for something else.