A skip list is a sorted, linked list of n nodes.

Each node can have many pointers:

standard linked-list node ( level 0 )

level 1 node

level 2 node

A level-k node has k + 1 pointers, each corresponding to a level:

A level-k pointer in a node with data d points to the following node of level  k, with data  d.

e.g.

A "header" node H has key  and points to the first node of each level.

The variable "MaxLevel" stores the maximum level in a list.

In a perfect skip list, a level-k node points to the  node past it.

 

Level	0	points to the	1st	node
"	1	"	2nd	"
"	2	"	4th	"
"	3	"	8th	"

 

Like so :

A skip list need not necessarily be perfect.
Node x has
key( x )
next( x, L)(the level - L pointer from x)

Idea
Search on the highest level as far as possible, then "drop down" and search on next level.
 

e.g. Search for 40

This results in the following code :

So in the previous picture -

 

Iteration	0	1	2	3	4	5	6
x at start	H	22	22	22	29	29	40

 

With each iteration, either -

	[A]	x moves forward in its current level
or	[B]	L moves down a level

In a perfect skip list -

MaxLevel  , so the total cost of all [B]'s is  O( log n ).
Moving forward in a level skips over half the nodes remaining to the right of x, so [A] occurs only once per level. Total cost of all [A]'s is thus  O( log n )

Insertion at the front of a perfect skip list requires "shifting" all the data (but not the nodes) one node to the right: cost  O( n )!

Solution
Don't use perfect skip lists. When inserting , choose the new node's level randomly !

Based on the observation that (in a perfect list)  of all nodes are level-0,  are level-1, etc :

 

level	probability
0
1
2
...	...
k

 

Idea
- Flip a coin until it lands 'heads'.
- The level obtained is the number of flips - 1.

Idea
- Traverse the list as we did in 'Search'.
- Every time we go down a level,remember where the pointer was.
- Update those pointers when the new node is created.

from [Weiss], inserting 22 :

*d_sL09*

Remember the pointers :

Nodes[ 2 ] = node 13
Nodes[ 1 ] = node 20
Nodes[ 0 ] = node 20

where Nodes[ i ] is the node at which x was when the level went from i to i-1.

In practice, this looks something like this :

e.g.

Now let's go back and trace the example from Weiss above :

With NewLevel = 2, we find -

Iteration	x	L	action
1	H	3	advance x
2	13	3	decr L
3	13	2	Nodes[ 2 ]  13, decr L
4	13	1	advance x
5	20	1	Nodes[ 1 ]  20, decr L
6	20	0	Nodes[ 0 ]  20, decr L
7	20	-1	exit loop

To create n :

Next( n, 2 )  NULL; Next( 13, 2 )  n
Next( n, 1 )  29; Next( 20, 1 )  n
Next( n, 0 )  23; Next( 20, 0 )  n

Skip List Analysis

Insert and Delete take time proportional to Search : they search, then update at most MaxLevel pointers - so we'll just analyze Search( ).

Lemma 1
Let Level( x ) be the level of node x.

P( Level( x )  i ) = 

Intuition :

Lemma 2
In a list of n nodes, E( MaxLevel ) 

Intuition (no proof ) :
In a list of n nodes, the number of nodes of each level is expected to be

 

Level	E( # of nodes of that level )
0	n
1	n
2	n
k
log n -1	= 1
log n	=
log n +1	=

 

Theorem
In a skip list of n nodes, the expected time of Search, Insert, and Delete is O( log n ).

Let's follow the header-to-element path backward from the element.

e.g.Search( 45 )

 

Node	Level	Action
45	0	back
44	0	up
44	1	back
29	1	back
22	1	up
22	2	up
22	3	back
H	3

 

Expected search time is equal to the expected number of 'back' and 'up' steps.

Observation
In following the path backward, at node x and level L, we -
- go back if level( x ) = L
- go up if level( x ) > L

 

 

 

P( back ) =  andP( up ) = 

Let C( k ) be the expected length of a path that rises k levels.
(e.g. in the previous diagram, we rose 3 levels = MaxLevel - 0)

Then
C( k ) = P( back ) * ( 1 step back + C( k ) )
+ P( up ) * ( 1 step up + C( k-1 ) )

=  ( 1 + C( k ) ) +  ( 1 + C( k-1 ) )

= 1 +  C( k ) +  C( k-1 )

= 2 + C( k-1 )

= 2 ksince C( 0 ) = 0

A path rising k levels has expected length 2 k.

Let's follow the path back until we reach level  (expected MaxLevel).

expected cost = 

- but we might not be at the header yet. We must follow the pointers back to the header, going through nodes of level  .

expected cost  expected number of nodes
of level 

= 

= 

expected cost  2 log n + 2 

which  O( log n ), thus -

Skip list operations take expected time O( log n )!

The key to the proof is in counting the path length backward.

 

BSP	- randomized insertion order  - expected tree size O( n log n )
Universal Hashing	- randomized hash function  - probability of collision is
Skip List	- randomized level of new node  - expected running time O( log n )

In general :
No upper bounds, so we could have a bad 'worst case' performance in some (infrequent) cases.

The randomization makes the algorithm immune to 'bad input' which, without randomization, would cause poor performance.

In the examples above, there is no input guaranteed to cause bad performance.

Randomized algorithms are often quite simple to implement.

'Quicksort' is another example.

Copyright 1998
James Stewart
Dynamic Graphics Project
Department of Computer Science
University of Toronto