Mailinglist Archive: opensuse (3354 mails)

< Previous Next >
Re: [opensuse] Double Linked List patented in 2006
  • From: Matthias Hopf <mhopf@xxxxxxx>
  • Date: Tue, 20 Mar 2007 12:52:30 +0100
  • Message-id: <20070320115230.GA10090@xxxxxxx>
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 <mhopf@xxxxxxx>      __        __   __
Maxfeldstr. 5 / 90409 Nuernberg   (_   | |  (_   |__          mat@xxxxxxxxx
Phone +49-911-74053-715           __)  |_|  __)  |__  R & D   www.mshopf.de
-- 
To unsubscribe, e-mail: opensuse+unsubscribe@xxxxxxxxxxxx
For additional commands, e-mail: opensuse+help@xxxxxxxxxxxx

< Previous Next >
Follow Ups