Why doesn't exist not concurrent version of SkipList

Question

I began research ConcurrentSkipListSet.

From begining I tried to understand what does SkipList is ?

I imagine it so(possible variant):

I have 2 questions:

1. How does SkipList relates with Concurrency ?
2. Why does not exis not Concurrent variant of this data structure?

Answer 1

Your skip list is a bit off, it looks more like:

^{_{From http://en.wikipedia.org/wiki/File:Skip_list.svg}}

The bottom starts out like a link list, and you've got that... but think of them more as towers that are linked to for each level. The thing here is that if you wanted to find 7 you can skip from 1 -> 4 -> 6 -> 9 (oops, nope), to 7. This lets you approximate a balanced binary tree with linked lists.

With a red-black or AVL tree, when one needs to modify the structure it is necessary to lock it entirely down so that the structure can be re-arranged. On the other hand, a skip list can be 'rearranged' without a global lock. A delete of 7 requires only changing the links pointing to it to point to the next element, which requires only a write lock on the 6 element, not the entire structure.

A good read on skip lists, where they were introduced, is Skip Lists: A Probabilistic Alternative to Balanced Trees which shows how it works and various algorithms. Within this is "Table 2 - Timings and implementations of different algorithms" which shows Skip Lists running quite a bit faster, though some of that was because of the particular data they were using.

In the 'Additional work on skip lists"

I have described a set of algorithms that allow multiple pro- cessors to concurrently update a skip list in shared memory [Pug89a]. This algorithms are much simpler than concurrent balanced tree algorithms. They allow an unlimited number of readers and n busy writers in a skip list of n elements with very little lock contention.

This leads to another article titled Concurrent Maintenance of Skip Lists which delves specifically into a structure with multiple readers and writers working through. This goes into looking at how long writers need to wait for a lock and how fast the speed up overall of the structure.

And so, because of these properties, it allows for multiple readers and writers in the structure with minimal locking and structure balancing.

As to the why isn't there a non-concurrent skip list in the Java Library? It would mean duplicating the code to another package (which is bad) and wouldn't really gain anything. There is nothing saying you can't use a concurrent package somewhere that isn't constrained by concurrent issues. The thing is they needed two types of Map for concurrent work, an O(1) HashMap and an O(log n) tree. Since the TreeMap wouldn't make for a good concurrent implementation, they decided to change this to a SkipList.

Related reading:

• How to implement lock-free skip list
• lock-free skiplist with rank operation

Answer 2

1. Any data structure is independent of concurrency. See the Java List implementations in the collections package. LinkedList is not thread-safe, but you can make it so using the Collections class.
2. The individual who wrote the implementation for SkipList decided to build thread safety into the class. That was an implementation decision.