Mailinglist Archive: opensuse (3354 mails)

< Previous Next >
Re: [opensuse] Double Linked List patented in 2006
  • From: Randall R Schulz <rschulz@xxxxxxxxx>
  • Date: Mon, 19 Mar 2007 15:36:43 -0700
  • Message-id: <200703191536.43766.rschulz@xxxxxxxxx>
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: opensuse+unsubscribe@xxxxxxxxxxxx
For additional commands, e-mail: opensuse+help@xxxxxxxxxxxx

< Previous Next >
Follow Ups
References