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. That's poor explanation, but it is vaguely like the data structure described earlier in this thread and illustrates an openly published data structure that is significantly more subtle and less obvious than the one here. > For example, does it occur in standard textboooks on computer > programming and data structures? Is there long-standing open > source software in which it may be found? Skip lists appear extensively in the computing literature, but are a relatively new invention by comparison to other basic linked structures. They are credited originally to Willilam Pugh in 1990. (See <ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf>). It has since spawned follow-on research to elaborate or modify the basic structure (e.g., to allow for fast concurrent access and update). 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). > Thanks! > Ted. Randall Schulz -- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
