[concurrency-interest] Skip Lists, Concurrent Skip Lists and Concurrent Sorted Maps

Bill Pugh pugh@cs.umd.edu
Fri, 18 Jun 2004 12:56:08 -0400


On Jun 18, 2004, at 11:09 AM, Mike Skells wrote:
>>
>> It would also be nice to expose methods that, given a key k,
>> return the entry with the smallest key > k, and another method that
>> returns the entry
>> with the largest key < k. (Methods like this exist in the current
>> TreeMap implementation,
>> but are private).
>>
>> We might also release a nonconcurrent SkipList. For example,
>> that would
>> allow you
>> to perform rank queries (get me the entry at position 42).  Rank
>
> I don't understand this. From my understanding a rank query is
> List.get(int)
> which is inefficent for a skip list, as it has to scan every node like 
> a
> linked list doesn't it,
> As the skiplist doesn't know its position due to the random nature of
> the skipping?
>

You can implement a skip list that can efficiently perform rank queries.

See the skip list cookbook, section 3.4
	ftp://ftp.cs.umd.edu/pub/skipLists/cookbook.pdf