I'm learning about circular queues. Which implementation of circular queue is best, the array implementation or linked list implementation?
A:
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'.
Skilldrick
2010-08-21 11:42:52
Ya you r right.But we can also make some modifications to normal queue program such that when the last index reached in the array we can make the array index pointer to point to the first index of the array.So that it works perfectly as a circular queue.clarification for BEST:Best in terms of data accessing speed and memory management.
NEO
2010-08-21 11:57:11
You still have not really clarified what you mean by best: obviously speed is important, and memory management isn't really a metric. Fyi, this is also often called a ring-buffer.
Noah Watkins
2010-08-21 20:57:52
A:
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).
judda
2010-08-21 21:01:17
A:
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.
Daniel Stutzbach
2010-08-21 21:27:06