11/22/23, 8:23 PM Skip List | Brilliant Math & Science Wiki

Skip List

The skip list is a probabilisitc data structure that is built upon the general idea of a linked list. The skip list uses proba
build subsequent layers of linked lists upon an original linked list. Each additional layer of links contains fewer eleme
new elements.

You can think about the skip list like a subway system. There's one train that stops at every single stop. However, there
express train. This train doesn't visit any unique stops, but it will stop at fewer stops. This makes the express train an a
option if you know where it stops.

Skip lists are very useful when you need to be able to concurrently access your data structure. Imagine a red-black tre
implementation of the binary search tree. If you insert a new node into the red-black tree, you might have to rebalan
entire thing, and you won't be able to access your data while this is going on. In a skip list, if you have to insert a new
the adjacent nodes will be affected, so you can still access large part of your data while this is happening.

Contents
Properties
Time and Space Complexity

Algorithm Pseudocode
Height of the Skip List
Proving Complexity

References

Properties

A skip list starts with a basic, ordered, linked list. This list is sorted, but we can't do a binary search on it because it is a
and we cannot index into it. But the ordering will come in handy later.

Then, another layer is added on top of the bottom list. This new layer will include any given element from the previou
probability p. This probability can vary, but oftentimes 12 is used. Additionally, the first node in the linked list is often a
​

as a header for the new layer. Take a look at the following graphics and see how some elements are kept but others a
discarded. Here, it just so happened that half of the elements are kept in each new layer, but it could be more or less
probabilistic. In all cases, each new layer is still ordered.

An example implementation of a skip list [1]

A skip list S has a few important properties that are referenced in its analysis. It has a height of h which is the numbe
lists in it. It has a number of distinct elements, n. And it has a probability p, which is usually 12 . ​

The highest element (one that appears in the most lists) will appear in log 1 (n) lists, on average--we'll prove this late
p ​

1
use p = 2 , there are log2 (n) lists. This is the average value of h. Another way of saying "Every element in a linked list
​ ​

linked list below it" is "Every element in level Si+1 exists in level Si ."
​ ​

Each element in the skip list has four pointers. It points to the node to its left, its right, its top, and its bottom. These q
will allow us to efficiently search through the skip list.

https://brilliant.org/wiki/skip-lists/#:~:text=The skip list is a,elements%2C but no new elements. 1/4

11/22/23, 8:23 PM Skip List | Brilliant Math & Science Wiki

Time and Space Complexity

Time

The complexity of a skip list is complicated due to its probabilistic nature. We will prove its time complexity below, bu
we will just look at the results. It is important to note, though, that these bounds are expected or average-case bound
because we use randomization in this data structure:

Insertion - O( log(n)), Deletion - O( log(n)),

Indexing - O( log(n)), Search - O( log(n)).
​ ​ ​

The worst-case bounds for the skip list are below, but we won't worry about these for analysis:

Insertion - O(n), Deletion - O(n),

Indexing - O(n), Search - O(n).
​ ​

Space

Space is a little easier to reason about. Suppose we have the total number of positions in our skip list equal to

h
1
n∑ .
2i
​ ​

i=0

That is equal to

1 1 1
n ⋅ (1 + + + + ⋯) = n ⋅ 2
2 4 8
​ ​ ​

because of the infinite summation. Therefore, our expected space utilization is simply

​ Space - O(n). ​

This is also not concrete. Probabilistically, our skip list could grow much higher. However, this is the expected space co

Algorithm Pseudocode

There are four main operations in the skip list.

Search

The input to this function is a search key, key . The output of this function is a position, p , such that the value at this p
the largest that is less than or equal to key .

1 Search(key)
2 p = top-left node in S
3 while (p.below != null) do //Scan down
4 p = p.below
5 while (key >= p.next) do //Scan forward
6 p = p.next
7 return p

Essentially, we are scanning down the skip list, then scanning forward.

Indexing

This functions in the exact same way as Search , so we will omit the code.

https://brilliant.org/wiki/skip-lists/#:~:text=The skip list is a,elements%2C but no new elements. 2/4

11/22/23, 8:23 PM Skip List | Brilliant Math & Science Wiki

Insertion

The input for insertion is a key . The output is the topmost position, p , at which the input is inserted. Note that we are
Search method from above. We use a function called CoinFlip() that mimics a fair coin and returns either heads or tails
the function insertAfter(a, b) simply inserts the node a after the node b .

1 Insert(key)
2 p = Search(key)
3 q = null
4 i = 1
5 repeat
6 i = i + 1 //Height of tower for new element
7 if i >= h
8
h = h + 1
9
createNewLevel() //Creates new linked list level
10
while (p.above == null)
11
p = p.prev //Scan backwards until you can go up
12
p = p.above
13
q = insertAfter(key, p) //Insert our key after position p
14
until CoinFlip() == 'Tails'
15
n = n + 1
16
return q

First, we always insert the key into the bottom list at the correct location. Then, we have to promote the new element
by flipping a fair coin. If it comes up heads, we promote the new element. By flipping this fair coin, we are essentially
how big to make the tower for the new element. We scan backwards from our position until we can go up, and then w
level and insert our key right after our current position.

While we are flipping our coin, if the number of heads starts to grow larger than our current height, we have to make
create new levels in our skip list to accommodate this. Lines 7-9 of this function take care of that for us.

Deletion

Deletion takes advantage of the Search operation and is simpler than the Insertion operation. We will save space by w
pseudocode more verbosely.

1 Delete(key)
2 Search for all positions p_0, ..., p_i where key exists
3 if none are found
4 return
5 Delete all positions p_0, ..., p_i
6 Remove all empty layers of skip list

Delete can be implemented in many ways. Since we know when we find our first instance of key , it will be connected
others instances of key , and we can easily delete them all at once.

Height of the Skip List

Earlier, we said that there will be log2 (n) lists in total. But why? If each newly created level is done so probabilistically
​

we know that?

The probability Pi that an element in skip list S with n total elements gets up to level i is just
​

1
Pi =
2i
​ ​

because if the probability is 12 , then to create a new level, we're tossing a coin for each element to see if it should be
​

So, the probability that at least one of the n elements gets to level i is

https://brilliant.org/wiki/skip-lists/#:~:text=The skip list is a,elements%2C but no new elements. 3/4

11/22/23, 8:23 PM Skip List | Brilliant Math & Science Wiki
n
Pi ≤ .
2i
​ ​

Let's try some numbers to see what this means. If i = log2 (n), then
​

n
Pi ≤ = 1.
2log2 (n)
​ ​

If i increases slightly to i = 3 ⋅ log2 (n), then

​

n 1
Pi ≤ = .
23 log2 (n) n2
​ ​ ​

This means, that if n = 1000, there is one in a million chance of any one particular element making it to the top laye
analysis, of course, is not strict, but with a high probability (a word used often in randomized algorithms), S has a hei
log2 (n).
​

Proving Complexity

As we discussed earlier, the worst-case scenario for skip lists is quite bad. In fact, the height of the skip list can stretch
∞ because we are using random coin flips. However, this analysis is not fair because skip lists perform much better o
Let's take the operation Search . This is the main focus of the skip list because both Insertion and Deletion are proved th
way.

Search

There are two nested while loops in this function. There is the outer loop that is akin to "scanning down" the skip list,
is the inner loop which is like "scanning forward" in the skip list.

We have proven above that the height h of the skip list is O( log2 (n)). So, the maximum number of moves down th ​

we can make is O( log2 (n)). ​

Now, let's bound the number of scans forward we can make. Let's say we scanned ni keys at level i before we droppe ​

level i − 1. Each subsequent key that we scan after we drop into this level cannot exist in level i, or otherwise we wou
already seen it. The probability that any given key in this level is in level i is 12 . That means the expected number of ke ​

be encountering in our new level once we've dropped down is 2, a O(1) operation.

So, our two steps of scanning down and scanning forward take O( log2 (n)) and O(1) time, respectively. That mean ​

time for search is O( log2 (n)). ​

If this analysis feels similar to binary search trees, that's because it is! If you look closely at the skip list, it resembles a
lower levels larger than higher levels.

References

1. Mula, W. Wikipedia Skip Lists. Retrieved April 20, 2016, from https://en.wikipedia.org/wiki/Skip_list

Cite as: Skip List. Brilliant.org. Retrieved 13:50, November 22, 2023, from https://brilliant.org/wiki/skip-lists/

https://brilliant.org/wiki/skip-lists/#:~:text=The skip list is a,elements%2C but no new elements. 4/4