John Meehan wrote:Thanks for that.
An additional question though... Is it just me or is this an awful way to use a linked list? Circular queues make sense for arrays, but for linked lists it just seems silly.
Steve
Steve
John Meehan wrote:There's a decent wiki explanation with pictures: http://en.wikipedia.org/wiki/Circular_queue#How_it_works
With linked lists, it would make sense to have a queue where the front and the end points to the same sentinel node, so queuing and de-queuing is just a matter of putting new nodes on one side of the queue and removing them from the other side.
But for some strange reason my professor wants something that looks like the array version instead. And my code just looks like moose droppings.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
Winston Gutkowski wrote:
Fine, but I doubt you'll have much joy basing it on LinkedList because it hides Nodes from you.
Furthermore, that class's implementation may be overkill since it is doubly-linked, whereas an LL-ring-based queue only really needs a forward pointer (oddly enough, I've been working on that very thing myself recently ).
Well, that link appears to have an explanation of how to do that too. One nice thing about an array is that it's simple and fast - and furthermore, if it's size is a power of 2, you can use bit masking to get your "circular index", which is about as fast as it gets in Java. On the other hand, it's more prone to concurrency bottlenecks.
John Meehan wrote:If you're using a singly-linked list, how do you add a to the end of the queue without traversing the entire list? Does your sentinel point to both ends simultaneously? Doesn't exactly make it a real singly-linked list then.
Like I said I did eventually get it to work, but I'd never use this for anything reasonable ever.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
Did you see how Paul cut 87% off of his electric heat bill with 82 watts of micro heaters? |