I'm wondering whether anyone here has ever used a skip list. It looks to have roughly the same advantages as a balanced binary tree but is simpler to implement. If you have, did you write your own, or use a pre-written library (and if so, what was its name)?
Asked
Active
Viewed 7,168 times
19
-
3See also http://stackoverflow.com/questions/256511/skip-list-vs-binary-tree – J D Aug 08 '10 at 00:14
7 Answers
17
My understanding is that they're not so much a useful alternative to binary trees (e.g. red-black trees) as they are to B-trees for database use, so that you can keep the # of levels down to a feasible minimum and deal w/ base-K logs rather than base-2 logs for performance characteristics. The algorithms for probabilistic skip-lists are (IMHO) easier to get right than the corresponding B-tree algorithms. Plus there's some literature on lock-free skip lists. I looked at using them a few months ago but then abandoned the effort on discovering the HDF5 library.
literature on the subject:
Papers by Bill Pugh:
- A skip list cookbook
- Skip lists: A probabilistic alternative to balanced trees
- Concurrent Maintenance of Skip Lists
non-academic papers/tutorials:
- Eternally Confuzzled (has some discussion on several data structures)
- "Skip Lists" by Thomas A. Anastasio
Jason S
- 184,598
- 164
- 608
- 970
-
By *alternative to binary trees*, did you mean *balanced binary trees* instead? – Naman Feb 12 '19 at 05:54
-
-
I was just going through it, and its most voted here. So thought of spending some time getting into the details. – Naman Feb 12 '19 at 13:41
9
Actually, for one of my projects, I am implementing my own full STL. And I used a skiplist to implement my std::map. The reason I went with it is that it is a simple algorithm which is very close to the performance of a balanced tree but has much simpler iteration capabilities.
Also, Qt4's QMap was a skiplist as well which was the original inspiration for my using it in my std::map.
Evan Teran
- 87,561
- 32
- 179
- 238
-
1
-
not quite yet, but things are almost to the point where i may release my STL. But there is plenty of example skip list implementations out there. – Evan Teran Feb 18 '10 at 16:40
-
Yes, there is plenty of skip list code available. I was looking for something that specifically complies with std::map<> interface. QMap looks quite close, so I'll give that a try. Thank-you – dkantowitz Feb 18 '10 at 18:11
8
Years ago I implemented my own for a probabilistic algorithms class. I'm not aware of any library implementations, but it's been a long time. It is pretty simple to implement. As I recall they had some really nice properties for large data sets and avoided some of the problems of rebalancing. I think the implementation is also simpler than binary tries in general. There is a nice discussion and some sample c++ code here:
http://www.ddj.us/cpp/184403579?pgno=1
There's also an applet with a running demonstration. Cute 90's Java shininess here:
http://www.geocities.com/siliconvalley/network/1854/skiplist.html
-
1I'm accepting this one because of the DDJ article it references. Apologies to Even and Steve, I'd accept all three answers if I could. – Head Geek Oct 25 '08 at 00:14
-
7
Java 1.6 (Java SE 6) introduced ConcurrentSkipListSet and ConcurrentSkipListMap to the collections framework. So, I'd speculate that someone out there is really using them.
Skiplists tend to offer far less contention for locks in a multithreaded situation, and (probabilistically) have performance characteristics similar to trees.
See the original paper [pdf] by William Pugh.
2
I implemented a variant that I termed a Reverse Skip List for a rules engine a few years ago. Much the same, but the reference links run backward from the last element.
This is because it was faster for inserting sorted items that were most likely towards the back-end of the collection.
It was written in C# and took a few iterations to get working successfully.
Naman
- 27,789
- 26
- 218
- 353
Steve Morgan
- 12,978
- 2
- 40
- 49
-
8Couldn't you invert the comparison for the type, and use a standard skiplist to achieve the same result? – oɔɯǝɹ Jul 11 '10 at 16:16
-
1@oɔɯǝɹ You could be right. But this Reverse Skip List might be more naturally compatible with SQL Server and other databases (so the database exactly mirrors the data). Sometimes it's the shape of code that makes a difference, sort of like a Tetris block. – MicroservicesOnDDD Jan 14 '20 at 19:47
2
The skip list has the same logarithmic time bounds for searching as is achieved by the binary search algorithm, yet it extends that performance to update methods when inserting or deleting entries. Nevertheless, the bounds are expected for the skip list, while binary search of a sorted table has a worst-case bound.
Devanshu
- 883
- 10
- 22
1
Skip Lists are easy to implement. But, adjusting the pointers on a skip list in case of insertion and deletion you have to be careful. Have not used this in a real program but, have doen some runtime profiling. Skip lists are different from search trees. The similarity is that, it gives average log(n) for a period of dictionary operations just like the splay tree. It is better than an unbalanced search tree but is not better than a balanced tree.
Every skip list node has forward pointers which represent the current->next() connections to the different levels of the skip list. Typically this level is bounded at a maximum of ln(N). So if N = 1million the level is 13. There will be that much pointers and in Java this means twie the number of pointers for implementing reference data types. where as a balanced search tree has less and it gives same runtime!!.
SkipList Vs Splay Tree Vs Hash As profiled for dictionary look up ops a lock stripped hashtable will give result in under 0.010 ms where as a splay tree gives ~ 1 ms and skip list ~720ms.
quiet_penguin
- 808
- 7
- 18