Re: C# Deque found on the web--thanks to The Game Programming Wiki

Peter Duniho <NpOeStPeAdM@xxxxxxxxxxxxxxxx> wrote:
Jon Skeet [C# MVP] wrote:
[...]
I *could* have used LinkedList for this (except that I originally wrote
it before 2.0, of course) but it feels more like a "queue with
occasional random access" than a normal linked list. (Finding the right
point to insert a new item is also quicker this way than with a linked
list.)

Well, you are free to call it a queue, of course. But it's not really a
queue, at least not a pure one. :)

I'm curious what it is about your implementation that makes insertion of
new items faster than if using a linked list?

The queue is ordered by priority, so it can use a binary search to find
the correct insertion point. Binary search on a linked list isn't
terribly fast :)

Admittedly it won't matter unless you've got thousands of items on the
queue...

--
Jon Skeet - <skeet@xxxxxxxxx>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too
.

Relevant Pages

  • Re: Decent datastructure for queue operations
    ... > the queue). ... Binary search tree might ... > - or if a binary search tree is really a great idea, ... For a priority queue, you need a more sophisticated data structure, ...
    (comp.lang.lisp)
  • Re: C# Deque found on the web--thanks to The Game Programming Wiki
    ... The queue is ordered by priority, so it can use a binary search to find the correct insertion point. ... And I'd suggest that a more traditional approach, maintaining an ordered list of queues would work fine too (assuming that for a given priority, tasks are still FIFO). ... The ordered list could be a SortedList if one wants, but I think a regular list maintained by insertion sort would be fine, given that the number of unique priorities is likely to be low. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Decent datastructure for queue operations
    ... Binary search tree might ... Use a queue data structure built on top of lists: ... the first and to the last last cons cell. ...
    (comp.lang.lisp)
  • Re: Decent datastructure for queue operations
    ... > FIFO data structure. ... So this is obviously not an ordinary queue. ... Regular Lisp lists can be used for FIFOs where the enqueue and dequeue ... The vector would have to be sorted in order to support a binary search. ...
    (comp.lang.lisp)
  • Re: C# Deque found on the web--thanks to The Game Programming Wiki
    ... Jon Skeet [C# MVP] wrote: ... I *could* have used LinkedList for this but it feels more like a "queue with occasional random access" than a normal linked list. ... I'm curious what it is about your implementation that makes insertion of new items faster than if using a linked list? ...
    (microsoft.public.dotnet.languages.csharp)