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