>> 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