Yesterday I was working on a small Haskell library for working with 
mutable double-linked lists. Man, it's been such a long time since I 
worked with this data structure, I'd forgotten how great it is!

OK, the down-side: Sequential access. You can only access lists 
sequentially. Obtaining the Nth element is a linear-time operation, and 
any attempt at parallel processing is fairly doomed from the start.

On the other hand, if you need to process *all* the data in your 
container anyway, being limited to only sequential access might not be 
all that bad. And you still have O(1) access to any node which you 
already happen to have a pointer to.

So there's a big down-side. Now what's the up-side? Well, lists are 
trivially resizeable. (That's an expensive operation for anything 
array-based.) And they support a large number of O(1) operations. 
Joining two lists is O(1). Splitting a list into two lists is O(1). 
Inserting or deleting elements is O(1). Adding or removing entire 
sublists is O(1). Moving a bunch of elements from one spot to another is 
O(1). All these rearrangements that would usually be quite expensive 
become O(1) on lists.

I'm enjoying myself here. Especially the bit where I implemented 
transactional lists, so all these sophisticated list manipulations are 
thread-safe without me having to worry about deadlock. I can even do 
stuff like "move to the next node in the list, or block until one is added".

Post a reply to this message

On 04/08/2011 09:03 AM, Invisible wrote:
>
> OK, the down-side: Sequential access. You can only access lists
> sequentially. Obtaining the Nth element is a linear-time operation, and
> any attempt at parallel processing is fairly doomed from the start.
>
Have you considered a skip list structure?
(http://en.wikipedia.org/wiki/Skip_list)

Post a reply to this message

>> OK, the down-side: Sequential access. You can only access lists
>> sequentially. Obtaining the Nth element is a linear-time operation, and
>> any attempt at parallel processing is fairly doomed from the start.
>>
> Have you considered a skip list structure?
> (http://en.wikipedia.org/wiki/Skip_list)

No - mainly because I've never heard of it. ;-)

However, according to Wikipedia, it does everything in logarithmic time. 
Well, so does a tree [assuming you can keep it balanced]. Haskell 
already has a bazillion different tree implementations [although I don't 
recall seeing a mutable one recently].

Post a reply to this message

On 04/08/2011 02:09 PM, Invisible wrote:
> No - mainly because I've never heard of it. ;-)
>
> However, according to Wikipedia, it does everything in logarithmic time.
> Well, so does a tree [assuming you can keep it balanced]. Haskell
> already has a bazillion different tree implementations [although I don't
> recall seeing a mutable one recently].

Skip lists structure is claimed to be so simple,
that it could be easily implemented within an hour
without a textbook  (http://goo.gl/yDqKJ).

Post a reply to this message

On 4/8/2011 6:09, Invisible wrote:
> However, according to Wikipedia, it does everything in logarithmic time.

It moves forward and back in linear time. It moves far forward in 
logarithmic time if you make it tall enough. It's like an unholy union of 
tree and list that automatically keeps itself balanced. It's worth reading 
about, because it's interesting and easy to understand.

The nice thing is a skip graph, which is as efficient as a skip list except 
you can make it distributed like a DHT.

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> Yesterday I was working on a small Haskell library for working with
> mutable double-linked lists. Man, it's been such a long time since I
> worked with this data structure, I'd forgotten how great it is!

then why not using a LISt Processing language? ;)

Post a reply to this message

On 09/04/2011 03:40 AM, nemesis wrote:
> Invisible<voi### [at] devnull>  wrote:
>> Yesterday I was working on a small Haskell library for working with
>> mutable double-linked lists. Man, it's been such a long time since I
>> worked with this data structure, I'd forgotten how great it is!
>
> then why not using a LISt Processing language? ;)

Because I prefer working with a system that offers static type 
guarantees? And thread safety? And sane syntax? And...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

On 09/04/2011 03:40 AM, nemesis wrote:
> Invisible<voi### [at] devnull>  wrote:
>> Yesterday I was working on a small Haskell library for working with
>> mutable double-linked lists. Man, it's been such a long time since I
>> worked with this data structure, I'd forgotten how great it is!
>
> then why not using a LISt Processing language? ;)

Also, as a mere technicality... Aren't lists in Lisp *single* linked 
rather than *double* linked?

Post a reply to this message

> It's worth
> reading about, because it's interesting and easy to understand.

By contrast, I didn't bother reading much further because it appears to 
be very complex and difficult to understand.

> The nice thing is a skip graph, which is as efficient as a skip list
> except you can make it distributed like a DHT.

What's a DHT when it's at home?

Post a reply to this message

On 4/12/2011 3:50, Invisible wrote:
>> It's worth
>> reading about, because it's interesting and easy to understand.
>
> By contrast, I didn't bother reading much further because it appears to be
> very complex and difficult to understand.

Well, come on. Look at the pictures and you can understand what's going on. :-)

>> The nice thing is a skip graph, which is as efficient as a skip list
>> except you can make it distributed like a DHT.
>
> What's a DHT when it's at home?

a Hash Table that's not Distributed?

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message