Those Data structures can not be learned from leetcode- Skiplist

LORY
3 min readOct 16, 2022

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

--

--

LORY

A channel which focusing on developer growth and self improvement