@pacohope said:
@asuffield said:@tster said:One thing I think of though. I don't know of any languages that allow this....snip...
It's a historical trick, from back when memory was measured in kilobytes and rented by the month from IBM. You can assume that if you have enough memory to operate a garbage collector, then you have enough memory to use a double-linked list like any sane person.
I can't imagine there being a use for it in modern software.
Again another sad detail from the actual situation. This ran on a 900MHz Pentium III with 512M of RAM. I don't think the memory situation was that dire. This queue, on the other hand, was a core part of their event loop and needed to execute fast. I'm not implying that some of the various suggestions here don't run fast enough. I'm just saying that if you had to pick space versus time on this system, time would win. Which is all the more reason we wanted to dope slap the developer who shaved a few bytes off the queue and got it wrong. He could have done a simple doubly-linked list and it would have been exactly what was called for.
Hmm, priority queue implemented as a linked list... Anyone heard of this new-fangled "Heap" data-structure. Perhaps I should patent it, since I know its more advanced than the recently patented Linked List.
If its NOT a priority queue, then an array list certainly would be more effecient than a linked list.