Those Data structures can not be learned from leetcode- Skiplist

A better concurrency friendy data structure than B Tree.

In previous article — B Tree Step by Step . you can see it is a high performance data structure for searching .however:

• It is complex .
• when dealing with rebalance. the cost is high.
• what if under multi-processing (threading) environment ? it is even more compex .

In this article I only need your 5 mins time to walk through another Data structure which is simple (compare to B tree) yet powerful ,kind of a “multi-level link list” — Skiplist .

Let’s start.

A Skip Lists Sample

Attributes of skip list :

• Keys in sorted order.
• O(log n) levels
• Each higher level contains 1/2 the elements of the level below

Sample :

To build a perfect linked list. can start from bottom (which is a normal link list). then every upper layer link half of the elements . (as showing above)

Now lets see some operation .

Search

It’s simple. max visit log(N) levels then find the value : when value < current, go next level; otherwise check next node .

Insert

Step1: Locate the index to insert .

Step2: Build the link for each level. (Adjustment)

Depends on the position to insert, Need adjust(add/remove) max log(N) node links .

After insert (and rebuild links):

Delete