On Mar 19, 07 15:36:43 -0700, Randall R Schulz wrote: > On Monday 19 March 2007 13:37, Ted Harding wrote: > > So my question, for clarification, is: Can anyone supply any > > reference of sufficiently long standing to demonstrate that > > the second kind of "double linked list" at [2] above is well > > established prior art? > > You might want to read about "Skip Lists." They're a way of an ordered > collection starting with a conventional linked list augmented by layers > of extra links. Each successively layer skips further per link. It's > kind of like an ordered tree with each depth of the tree represented by > a separate linked list.
I thought about that as well, but skip lists are single linked lists, so this doesn't perfectly hold. > I've implemented Skip Lists as an experiment to find a fast and stable > priority queue. They can be made stably sorted, but do not appear to be > faster than a heap-based priority queue (which is not stably ordered). I found skip lists about an order of magnitude both faster and smaller in code footprint than any balanced tree algorithm I've seen so far - and balanced trees is IMHO the only competing algorithmic class. Also, memory footprint is much smaller with skip lists (1.333 pointers in average per node). Implementation is close to trivial, and it's almost impossible introduce bugs in the code (if you don't count the random generator which can easily be broken ;) Also they allow for O(1) access to the highest element, which is often very useful. What exactly do you refer to as a priority queue? Queues can be implemented in a number of different ways... Matthias -- Matthias Hopf <[EMAIL PROTECTED]> __ __ __ Maxfeldstr. 5 / 90409 Nuernberg (_ | | (_ |__ [EMAIL PROTECTED] Phone +49-911-74053-715 __) |_| __) |__ R & D www.mshopf.de -- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
