Which implementation of circular queue is best?

I'm learning about circular queues. Which implementation of circular queue is best, the array implementation or linked list impl开发者_JS百科ementation?

I would say that the linked list version would be the better of the two solutions for the fact that you don't have to keep adjusting the memory which your own to allow more elements into your array. As well as what Skilldrick said about in a linked list, about it actually pointing to where it belongs (last node points to the first thus making it circular).

If you do it in a linked list then it can actually be circular, because the last node will point to the first. But I think you need to clarify what you mean by 'best'.

It depends on which operations you will need to perform on the circular list. For example, if you need need random access ("give me the 237th item of the list") then the array implementation is going to be a lot faster.

On the other hand, with an implement you may need to sometimes resize the list, which will be slow. You can amortize that to get O(1) amortized time per insert, but on a real-time system the occasional slow operation may be unacceptable.

Circular queue is a bounded queue which implements arrays.

It is better than a normal queue because in this we can effectively utilise the memory space.If we have a normal queue and have deleted some elements from there then empty space is created there and even if the queue has empty cells then also we cannot insert any new element because the insertion has to be done from one side only(i.e rear or tail) and deletion has to be done from another side(i.e front or head).But in case of circular queue the front and rear are adjacent to each other.