Skip List
William Pugh, 1989
Background
› A skip list is a randomly built binary search tree
› The expected time complexity to insert and remove an item from the skip list is O(log n)
› Inspired as a generalization of the singly-linked list
Consider the following linked list
head
Item
10
20
30
40
50
60
Height
1
1
1
1
1
1
Next
●
Node
In the worst case, it takes O(n) time to:
1) insert an item,
2) find an item, and 3) remove an item
What if we added a level to node 40?
head
Next
Item
10
20
30
40
50
60
Height
1
1
1
2
1
1
0
●
1
●
What if we added two levels to node 20?
head Next
Item
10
20
30
40
50
60
Height
1
3
1
2
1
1
0
●
1
●
2
head Next
Item
10
20
30
40
50
60
Height
1
3
1
2
1
1
0
●
1
●
2
●
What if we added two levels to node 60?
head Next
Item
10
20
30
40
50
60
Height
1
3
1
2
1
3
0
●
1
●
2
●
head Next
Item
10
20
30
40
50
60
Height
1
3
1
2
1
3
0
●
1
●
2
●
What if we added three levels to node 50?
head Next
Item
10
20
30
40
50
60
Height
1
3
1
2
4
3
0
●
1
2
●
●
3
head Next
Item
10
20
30
40
50
60
Height
1
3
1
2
4
3
0
●
1
2
●
●
3
●
Can you see the binary search tree?
head Next
Item
10
20
30
40
50
60
Height
1
3
1
2
4
3
0
●
1
2
●
●
3
●
Can you see the binary search tree?
head Next
Item
10
20
30
40
50
60
Height
1
3
1
2
4
3
0
●
1
2
●
●
3
●
Root
Methods
› void Insert (T item)
– inserts item into the skip list (duplicate items are permitted)
› bool Contains (T item)
– Returns true if item is found; false otherwise
› void Remove (T item)
– Removes one occurrence of item (if possible)
Starting from scratch
4
●
3
●
2
●
1
●
0
●
—
—
Node Next[ ] int Height
Node class
head T Value
maxHeight = 0 // current maximum height of the skip list
Insert 30
The height of a node is randomly
set according to the following distribution
Height
Probability
1
1/2
2
1/4
3
1/8
4
1/16
h
1/2h
4
●
3
●
2
●
1
●
0
●
—
—
but is capped at one more than the current maxHeight of the skip list
0
●
1
30
head
maxHeight = 0
Insert 30
4
●
3
●
2
●
1
●
0
●
—
—
0
●
1
30
head
maxHeight = 1
Insert 30
cur
4
●
3
●
2
●
1
●
0
●
—
—
newNode.Next[i] = cur.Next[i]; cur.Next[i] = newNode;
0
●
1
30
head
maxHeight = 1
Insert 30
4
3
2
1
0
●
●
●
●
newNode.Next[i] = cur.Next[i]; cur.Next[i] = newNode;
0
●
—
head
maxHeight = 1
1
—
30
Insert 40
4
3
2
1
0
●
●
●
1
●
0
●
2
40
●
0
●
head
—
1
—
30
maxHeight = 2
Insert 40
cur
4
3
2
1
●
0
●
2
40
1
0
●
●
●
0
●
—
head
maxHeight = 2
●
1
—
30
Insert 40
cur
4
3
2
1
0
●
●
●
●
1
0
0
—
head
maxHeight = 2
1
2
●
●
—
30
40
Insert 40
cur
4
3
2
1
0
●
●
●
while (cur.Next[i] != null && cur.Next[i].Item.CompareTo(item) < 0) cur = cur.Next[i];
●
1
0
0
--
head
maxHeight = 2
1
2
●
●
--
30
40
Insert 40
4
3
2
1
0
●
●
●
cur
●
1
0
0
--
head
maxHeight = 2
1
2
●
●
--
30
40
Insert 40
4
3
2
1
0
●
●
●
cur
1
●
0
0
●
--
head
maxHeight = 2
1
2
--
30
40
Insert 60
cur
for (int i = maxHeight - 1; i >= 0; i–)
2
●
1
●
0
●
1
60
2
1
0
●
1
●
0
0
●
head
4
3
—
●
●
1
2
—
30
40
maxHeight = 3
Insert 60
cur
4
3
2
1
0
●
●
1
●
2
1
●
●
0
0
●
0
—
head
maxHeight = 3
1
2
1
●
—
30
40
60
Insert 60
cur
4
3
2
1
0
●
●
1
●
2
1
●
●
0
0
●
0
—
head
maxHeight = 3
1
2
1
●
—
30
40
60
Insert 60
4
3
2
1
0
●
●
1
cur
●
2
1
●
●
0
0
●
0
—
head
maxHeight = 3
1
2
1
●
—
30
40
60
Insert 60
4
3
2
1
0
●
●
1
cur
●
2
1
●
●
0
0
0
●
—
head
maxHeight = 3
1
2
1
—
30
40
60
Insert 60
4
3
2
1
0
●
●
1
cur
●
2
1
●
●
0
0
0
●
—
head
maxHeight = 3
1
2
1
—
30
40
60
Insert 60
4
3
2
●
●
cur
2
●
1
0
1
0
1
●
0
0
●
—
head
maxHeight = 3
1
2
1
—
30
40
60
Insert 10
cur
10 < 60 move down
4
3
2
1
●
●
2
●
1
1
●
0
0
●
0
0
0
●
--
head
maxHeight = 3
1
1
2
3
--
10
30
40
60
Insert 10
cur
10 < 40 move down
4
3
2
1
●
●
2
●
1
1
●
0
0
●
0
0
0
●
--
head
maxHeight = 3
1
1
2
3
--
10
30
40
60
Insert 10
cur
10 < 30 and height within range adjust references
4
3
2
1
●
●
2
●
1
1
●
0
0
●
0
0
0
●
--
head
maxHeight = 3
1
1
2
3
--
10
30
40
60
Insert 10
cur
4
3
2
1
●
●
newNode.Next[i] = cur.Next[i]; cur.Next[i] = newNode;
1
2
1
●
●
0
0
●
0
0
0
●
--
head
maxHeight = 3
1
1
2
3
--
10
30
40
60
Insert 10
cur
4
3
2
1
●
●
1
2
1
●
●
0
0
0
0
0
●
--
head
maxHeight = 3
1
1
2
3
--
10
30
40
60
Insert 50
cur
curr.Next[i] == null and height within range adjust references
2
1
0
●
0
0
0
0
●
0
●
head
4
3
--
●
1
1
2
4
3
--
10
30
40
50
60
maxHeight = 4
3
2
●
●
2
●
1
1
●
1
●
Insert 50
cur
4
3
2
1
0
●
1
0
3
2
●
●
●
2
●
1
1
●
0
0
0
●
0
●
head
--
1
1
2
4
3
--
10
30
40
50
60
maxHeight = 4
Insert 50
cur
50 < 60 and height within range adjust references
4
3
2
1
●
3
2
●
●
2
●
1
1
●
1
●
0
0
0
0
0
●
0
●
--
head
maxHeight = 4
1
1
2
4
3
--
10
30
40
50
60
Insert 50
cur
4
3
2
1
●
3
2
●
2
●
1
1
●
1
●
0
0
0
0
0
●
0
●
--
head
maxHeight = 4
1
1
2
4
3
--
10
30
40
50
60
Insert 50
cur
50 > 40 move across
4
3
2
1
●
3
2
●
2
●
1
1
●
1
●
0
0
0
0
0
●
0
●
—
head
maxHeight = 4
1
1
2
4
3
—
10
30
40
50
60
Insert 50
4
3
2
1
●
50 < 60 and height within range
adjust references
cur
1
3
2
1
●
●
2
1
●
●
0
0
0
0
0
●
0
●
--
head
maxHeight = 4
1
1
2
4
3
--
10
30
40
50
60
Insert 50
4
3
2
1
●
1
cur
3
2
1
●
2
1
●
●
0
0
0
0
0
●
0
●
--
head
maxHeight = 4
1
1
2
4
3
--
10
30
40
50
60
Insert 50
4
3
2
1
●
50 < 60 and height within range
adjust references
cur
1
3
2
1
●
2
1
●
●
0
0
0
0
0
●
0
●
--
head
maxHeight = 4
1
1
2
4
3
--
10
30
40
50
60
Insert 50
4
3
2
1
0
●
1
0
cur
3
2
1
●
2
1
●
●
0
0
0
0
●
--
head
maxHeight = 4
1
1
2
4
3
--
10
30
40
50
60
Insert 20
cur
4
3
2
1
0
1
●
●
●
1
0
3
1
●
2
2
2
1
●
●
0
0
0
0
0
●
--
head
maxHeight = 4
●
1
3
1
2
4
3
--
10
20
30
40
50
60
Insert 20
cur
4
3
2
1
0
1
●
●
●
1
0
3
1
●
2
2
2
1
●
●
0
0
0
0
0
●
--
head
maxHeight = 4
●
1
3
1
2
4
3
--
10
20
30
40
50
60
Insert 20
cur
4
3
2
1
0
●
2
●
●
1
0
3
●
2
2
0
●
1
1
1
●
0
0
0
0
●
head
--
1
3
1
2
4
3
--
10
20
30
40
50
60
maxHeight = 4
Insert 20
cur
4
3
2
1
0
●
2
1
●
●
1
0
3
2
1
●
2
1
●
●
0
0
0
0
0
●
--
head
maxHeight = 4
1
3
1
2
4
3
--
10
20
30
40
50
60
Insert 20
cur
4
3
2
1
0
●
2
●
1
0
3
●
2
2
●
1
1
1
●
0
0
0
0
0
●
--
head
maxHeight = 4
1
3
1
2
4
3
--
10
20
30
40
50
60
Insert 20
cur
4
3
2
1
0
●
2
●
1
0
3
●
2
2
●
1
1
1
●
0
0
0
0
0
●
--
head
maxHeight = 4
1
3
1
2
4
3
--
10
20
30
40
50
60
Insert 20
cur
4
3
2
1
0
●
2
1
●
1
3
2
1
●
2
1
●
●
0
0
0
0
0
0
●
--
head
maxHeight = 4
1
3
1
2
4
3
--
10
20
30
40
50
60
Insert 20
cur
4
3
2
1
0
●
1
1
0
3
●
2
2
2
1
●
1
●
0
0
0
0
0
●
--
head
maxHeight = 4
1
3
1
2
4
3
--
10
20
30
40
50
60
Final Skip List
4
3
2
1
0
●
2
1
0
3
●
2
2
●
1
1
1
●
0
0
0
0
0
●
--
head
maxHeight = 4
1
3
1
2
4
3
--
10
20
30
40
50
60
Phew!
Exercises (using the Final Skip List)
› Insert 35 with a height of 4.
› Insert 45 with a height of 1.
› Insert 40 with a height of 3 (a duplicated item).
› What is the maximum height of the next insertion?
› What is the probability that the height of the next node is 5? Be careful.
Contains 30
cur
30 < 50 move down
4
3
2
1
0
●
2
1
1
0
3
2
1
●
2
1
0
●
●
0
0
0
0
●
--
head
maxHeight = 4
1
3
1
2
4
3
--
10
20
30
40
50
60
Contains 30
cur
30 > 20 move across
4
3
2
1
0
●
2
1
1
0
3
2
1
●
2
1
0
●
●
0
0
0
0
●
—
head
maxHeight = 4
1
3
1
2
4
3
—
10
20
30
40
50
60
Contains 30
4
3
2
1
0
1
0
30 < 50 move down
cur
1
0
1
0
●
0
0
0
●
--
head
maxHeight = 4
●
1
2
3
1
2
3
2
4
●
2
3
●
1
--
10
20
30
40
50
60
Contains 30
4
3
2
1
0
1
0
30 < 40 move down
cur
1
0
1
0
●
0
0
0
●
--
head
maxHeight = 4
●
1
2
3
1
2
3
2
4
●
2
3
●
1
--
10
20
30
40
50
60
Contains 30
4
3
2
1
0
1
0
cur
1
0
1
0
●
0
0
0
●
--
head
maxHeight = 4
Found!
●
1
2
3
1
2
3
2
4
●
2
3
●
1
--
10
20
30
40
50
60
Exercises (using the Final Skip List)
› Show the sequence of references that are followed to find: – 60
– 30 – 10 – 70 – 45 – 35
› Draw two instances of the skip list where the Contains method takes linear time (i.e., O(n) steps).
Rules of thumb
› Drop down a level when the item you wish to insert, find, or remove is less than cur.Next[i].Item
– In the case of Insert, references are adjusted first when the height of the new node is within range
› Move across a level when the item you wish to insert, find or remove is greater than cur.Next[i].Item
› When the item is equal to curr.Next[i].Item:
– Insert:
– Contains: – Remove:
References are adjusted first when the height of the new node is within range (i.e. duplicate items)
Return true
cur.Next[i] = cur.Next[i].Next[i]
Starting with our final skip list
4
3
2
1
0
●
2
1
0
3
●
2
2
●
1
1
1
●
0
0
0
0
0
●
--
head
maxHeight = 4
1
3
1
2
4
3
--
10
20
30
40
50
60
Remove 20
cur
20 < 50 move down
4
3
2
1
0
●
2
1
1
0
3
2
1
●
2
1
0
●
●
0
0
0
0
●
--
head
maxHeight = 4
1
3
1
2
4
3
--
10
20
30
40
50
60
Remove 20
cur
20 found; adjust references and move down
4
3
2
1
0
●
2
1
1
0
3
2
1
●
2
1
0
●
●
0
0
0
0
●
--
head
maxHeight = 4
Found
1
3
1
2
4
3
--
10
20
30
40
50
60
Remove 20
cur
4
3
2
1
0
●
2
1
1
0
3
2
1
●
2
1
0
●
●
0
0
0
0
●
--
head
maxHeight = 4
1
3
1
2
4
3
--
10
20
30
40
50
60
Remove 20
cur
20 found; adjust references and move down
4
3
2
1
0
●
2
1
1
0
3
2
1
●
2
1
0
●
●
0
0
0
0
●
--
head
maxHeight = 4
Found
1
3
1
2
4
3
--
10
20
30
40
50
60
Remove 20
cur
4
3
2
1
0
●
2
1
0
3
●
2
2
●
1
1
1
●
0
0
0
0
0
●
--
head
maxHeight = 4
1
3
1
2
4
3
--
10
20
30
40
50
60
Remove 20
cur
20 > 10 move across
4
3
2
1
0
●
2
1
0
3
●
2
2
●
1
1
1
●
0
0
0
0
0
●
—
head
maxHeight = 4
1
3
1
2
4
3
—
10
20
30
40
50
60
Remove 20
4
3
2
1
0
●
20 found; adjust references and move down cur
2
1
1
3
2
1
●
2
1
●
●
0
0
0
0
0
0
●
—
head
maxHeight = 4
Found
1
3
1
2
4
3
—
10
20
30
40
50
60
Remove 20
cur
4
3
2
1
0
●
2
1
3
●
2
2
●
1
1
1
●
0
0
0
0
0
0
●
—
head
maxHeight = 4
1
3
1
2
4
3
—
10
20
30
40
50
60
Remove 20
4
3
2
1
0
●
1
0
3
2
1
●
2
1
●
●
0
0
0
0
●
—
head
maxHeight = 4
1
1
2
4
3
—
10
30
40
50
60
Remove 50
cur
4
3
2
1
0
●
1
0
3
2
●
2
0
●
1
1
●
0
0
0
●
—
head
maxHeight = 4
1
1
2
4
3
—
10
30
40
50
60
Remove 50
cur
4
3
2
1
0
●
●
1
0
3
2
1
●
2
1
●
●
0
0
0
0
●
head
—
1
1
2
4
3
—
10
30
40
50
60
maxHeight = 3
Note: maxHeight decreases by 1 whenever head.Next[i] is reset to null
Remove 50
cur
4
3
2
1
0
●
●
1
0
3
2
1
●
2
1
●
●
0
0
0
0
●
head
—
1
1
2
4
3
—
10
30
40
50
60
maxHeight = 3
Note: maxHeight decreases by 1 whenever head.Next[i] is reset to null
Remove 50
cur
4
3
2
1
0
●
●
1
0
3
2
1
●
2
1
●
●
0
0
0
0
●
—
head
maxHeight = 3
1
1
2
4
3
—
10
30
40
50
60
Remove 50
cur
4
3
2
1
●
1
3
2
●
2
1
●
1
●
0
●
0
0
0
0
0
●
—
head
maxHeight = 3
1
1
2
4
3
—
10
30
40
50
60
Remove 50
4
3
2
1
0
●
●
1
0
cur
3
2
1
●
2
1
●
●
0
0
0
0
●
—
head
maxHeight = 4
1
1
2
4
3
—
10
30
40
50
60
Remove 50
4
3
2
1
●
1
cur
3
2
●
2
1
●
1
●
0
●
0
0
0
0
0
●
—
head
maxHeight = 3
1
1
2
4
3
—
10
30
40
50
60
Remove 50
4
3
2
1
●
1
cur
3
2
●
2
1
●
1
●
0
●
0
0
0
0
0
●
—
head
maxHeight = 3
1
1
2
4
3
—
10
30
40
50
60
Remove 50
4
3
2
1
●
cur
3
2
●
2
●
1
1
1
●
0
●
0
0
0
0
0
●
—
head
maxHeight = 3
1
1
2
4
3
—
10
30
40
50
60
Remove 50
4
3
2
1
●
●
2
●
1
1
●
0
0
0
0
0
●
—
head
maxHeight = 3
1
1
2
3
—
10
30
40
60
Removing a duplicated item
› To remove one instance of a duplicate item from the skip list, some interesting and subtle issues arise
› Consider the following skip list where the item 20 is duplicated 4 times
To remove one instance of 20
4
3
2
1
0
●
2
1
1
0
3
2
1
●
2
1
0
●
●
0
0
0
0
●
—
head
maxHeight = 4
1
3
1
2
4
3
—
10
20
20
20
20
60
Remove one instance of 20
4
3
2
1
0
cur
●
●
2
1
0
Decrease the height of the node by one
●
0
0
0
0
0
●
—
head
maxHeight = 3
1
3
1
2
3
3
—
10
20
20
20
20
60
Decrease the maxHeight by one since cur.Next[3] == null
3
2
●
2
●
1
1
1
Remove one instance of 20
cur
4
3
2
1
0
●
●
2
1
1
3
2
1
●
2
1
●
●
0
0
0
0
0
0
●
—
head
maxHeight = 3
1
3
1
2
3
3
—
10
20
20
20
20
60
Remove one instance of 20
4
3
2
1
0
cur
●
●
Decrease the height of the node by one
2
1
0
3
2
●
2
●
1
1
1
●
0
0
0
0
0
●
—
head
maxHeight = 3
1
2
1
2
3
3
—
10
20
20
20
20
60
Remove one instance of 20
cur
4
3
2
1
0
●
●
2
1
1
3
2
1
●
2
1
●
●
0
0
0
0
0
0
●
—
head
maxHeight = 3
1
2
1
2
3
3
—
10
20
20
20
20
60
Remove one instance of 20
4
3
2
1
0
cur
●
●
Decrease the height
of the node by one (again)
2
1
1
3
2
1
●
2
1
●
●
0
0
0
0
0
0
●
—
head
maxHeight = 3
1
1
1
2
3
3
—
10
20
20
20
20
60
Remove one instance of 20
cur
4
3
2
1
2
1
1
3
2
●
2
1
●
1
●
0
●
0
0
0
0
0
0
●
—
head
maxHeight = 3
●
1
1
1
2
3
3
—
10
20
20
20
20
60
Remove one instance of 20
cur
4
3
2
1
0
●
●
2
1
1
3
2
1
●
2
1
●
●
0
0
0
0
0
0
●
—
head
maxHeight = 3
1
1
1
2
3
3
—
10
20
20
20
20
60
Remove one instance of 20
cur
4
3
2
1
●
2
1
1
3
2
●
2
1
●
1
●
0
●
0
0
0
0
0
0
●
—
head
maxHeight = 3
Decrease the height of the node by one
1
0
1
2
3
3
—
10
20
20
20
20
60
Skip list after removing one instance of 20
4
3
2
1
0
●
●
1
0
2
1
2
1
●
●
0
0
0
0
●
—
head
maxHeight = 3
1
1
2
3
3
—
10
20
20
20
60
Exercises (using the Final Skip List)
› Remove 60, 10, and 45.
› If maxHeight = 1 then show that Remove behaves exactly as the Remove method of a singly-linked list.
› If an item is duplicated in nodes of – increasing height
– decreasing height
show how one instance of the item is removed.
How to determine the random height?
› Strategy:
– Generate a positive random 32-bit integer R
– Let the height be the number of consecutive lower order bits that are equal to one
– Set the height of a node equal to min(height+1, maxHeight+1)
Example
0
1
0
0
0
0
1
1
1
0
0
0
1
0
1
0
1
1
1
0
1
1
1
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
R
1 R&1
height = 1;
R
1 R&1
height = 2;
R
1 R&1
height = 3;
R>>1 // right shift one place
0
0
1
0
0
0
0
1
1
1
0
0
0
1
0
1
0
1
1
1
0
1
1
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
R>>1 // right shift one place
0
0
0
1
0
0
0
0
1
1
1
0
0
0
1
0
1
0
1
1
1
0
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
R>>1 // right shift one place
0
0
0
0
1
0
0
0
0
1
1
1
0
0
0
1
0
1
0
1
1
1
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
R
1 R&1
Loop ends when R & 1 == 0 Height of the new node is set at 4
Implementation
int height = 0;
int R = rand.Next(); // R is a random 32-bit positive integer while ((height < maxHeight) && ((R & 1) == 1))
{
height++; // Equal to the number consecutive lower order 1-bits
R >>= 1; // Right shift one bit
}
if (height == maxHeight) maxHeight++;
Node newNode = new Node(item, height + 1);
* Expected time complexity
› Determined by the following loop structure
for(inti=maxHeight-1;i>=0;i–) //Down {
while (cur.Next[i] != null && cur.Next[i].Item.CompareTo(item) < 0) // Across cur = cur.Next[i];
... }
› Expected height of the skip list is O(log n)
– The for loop is expected to iterate O(log n) times
› The number of nodes at level i+1 is expected to be half the number of nodes at level i. Therefore, for each link at level i+1, there are an expected 2 links at level i.
– The while loop is expected to iterate O(1) times
› The overall expected time complexity is O(log n) for Insert, Contains, and Remove since all three methods use the loop structure on the previous slide