A recent assignment in my algorithms course asked us to design an efficient iterator for the backwards traversal of a skip list. Like any good student, the first thing I did was Google it. But I couldn’t find anything at all - no BB questions, definitely no answers (aside: I did come across this blog - a pretty good personal blog on programming by a vigorously self-studying Latvian - and this skip list article in particular.).
So to help future students I’m going to post my solution. This is meant only to stimulate thought and to share how I tackled it - by no means is it correct. I only handed it in yesterday, it hasn’t been marked yet. In fact, there is an absolutely crucial sub-part (the ‘truncated search’) that I didn’t have time to formally prove as being O(1), which is required (If you have a proof, please post it!). The whole thing hinges on this and it is only now ‘intuitively’ O(1).
A Short review of skip lists
A skip list is a data structure that offers, with a very high probability, performance similar to that of a balanced tree (O(lgn) Insert, Search, Delete) but is quite a bit easier to implement. It also offers certain advantages over trees, especially in applications such as parallel and network computer, since insertions and deletions can be done without having knowledge of the entire list.
The basic skip list is just an augmented singly-linked list. Certain nodes have i extra pointers, each pointing to the next node with at least i pointers (e.g. a Node with three pointers will point to the next node with 1, the next with at least 2 levels with pointer 2, and the next with at least 3 levels with pointer 3). This allows search (and therefore insert and delete) to skip over large chunks of the list by taking the fast-lane pointers whenever able.
A simple skip list with 10 nodes, from Wikipedia
The basic skip list algorithms are (taken from my course notes, with permission):
SkipListSearch(S, x)
//
// Find the node containing element "x". Also build array
// "Pointer" with the node we were at when we went "down"
// from level lev.
//
Let N ← head(S)
lev ← maxLevel(S)
Do
//
// Go right as far as possible.
//
While (element(nextNode(N, lev)) < x) do
N ← nextNode(N, lev)
//
// Now try on the next level down.
//
Pointer[lev] ← N
lev ← lev - 1
While (lev > 0)
If element(nextNode(N, 1)) = x then
Return nextNode(N, 1)
Return null
End
SkipListDelete(S, x)
//
// Find where x is (assume it is in the skip list).
//
N ← SkipListSearch(S, x)
//
// Fix the pointers that used to point to N.
//
For lev ← level(N) downto to 1 do
nextNode(Pointer[lev], lev) ← nextNode(N, lev)
//
// Deal with possible decrease in value of MaxLevel.
//
While nextNode(head(S), maxLevel(S)) = null do
decrement maxLevel(S)
End
SkipListInsert(S, x)
// Find where x is (assume it is not in the skip list).
//
SkipListSearch(S, x)
// Create new node with Pr{level > i} = p^i
// Common value for p is 0.5
lev ← 1
While random(1, 1/p) = 1 and level < levelCap do
increment lev
N ← new node with element x and level lev
// Fix the pointers that will now point to N
//
For lev ← min(level(N), maxLevel(S)) downto to 1 do
nextNode(N, lev) ← nextNode(Pointer[lev], lev)
nextNode(Pointer[lev], lev) ← N
// Deal with possible increase in the number of levels.
//
While level(N) > maxLevel(S) do
increment maxLevel(S)
nextNode(N, maxLevel(S)) ← null
nextNode(head(S), maxLevel(S)) ← N
End
A backwards iterator
The problem is to design an efficient backwards iterator for a skip list. Specifically, it needs to have three operations:
- init(), which initializes the skip list such that the next call to previous() returns the last element
- hasPrevious(), which returns true iff the next call to previous() will return a valid node
- previous() returns the next element in the skip list, moving backwards
The restriction is that n calls to previous (to traverse the whole list) runs in O(n).
Note this is almost trivial if traversing forwards - just follow all the pointers at the bottom level. Backwards is more tricky.
Oh ya and we also can’t have worse than Omega(n) space complexity, or restructure the skip list. This is too bad because there are two simple solutions that meet the O(n) restriction:
- Traverse the list forwards, pushing each element onto a stack. Pop off the stack.
- Add some lines to SkipListInsert so that the bottom level is a doubly instead of a singly linked list.
We are, however, allowed to alter the search algorithm.
An O(nlgn) solution
As a warm up, here’s an easy O(nlgn) solution: Go to the end of the list (go right as far as possible, go down. repeat until level = 0). The array Pointer (hereafter referred to as P[]) will then be pointing at the node containing the last element in P[1]. Then search for the last element. Now P[1] will point at the (node containing the) second last element. Doing this repetively, you will visit every node in reverse. That’s a cost of O(lg) for n elements, giving a total running time of O(nlg)
An O(n) solution
Look at the skip list above. Trace the search path for element 9, 8, and 7: the paths are almost identical. Note also that the pointer array, aside from P[1], will be populated with exactly the same elements in each search, precisely P[4]->1 P[3]->6 P[2]->6
What we need to do is eliminate the repeated steps. So we need to modify the search algorithm slightly so that we can specify from where in the list to start our search. Then, if we know the last common ‘down’ node in a path, we can just start our search from there. E.g. Once we’ve searched for 9, we could just search for 8 and 7 starting from node 6 since everything before it would be repeated. So let’s define
SkipListSearch2(S, start, x)
// Identical to SkipListSearch, but replace the very first line with
Let N ← start
//everything else the same as SkipListSearch
End
This is just a generalization; we could define:
SkipListSearch(S, x){ return SkipListSearch2(S, head(S), x); }
Ok, so once we have that all we have that we can write the full solution:
init()
// This is just a slight modification of the first search algorithm
lev ← maxLevel(S)
Do
//
// Go right as far as possible.
//
While (nextNode(N, lev) != nil) do
N ← nextNode(N, lev)
//
// Go down.
//
Pointer[lev] ← N
lev ← lev - 1
While (lev > 0)
End
hasPrevious()
return not P[1] = head // could be null, or a special head value
End
prevous()
// Save element to return. We're going to mess with the Pointer array
to_return ← element(P[1])
// Find most recent ‘down’ node (not including the current one at P[1])
i ← 2
while (i <= maxLevel(S) and P[i] = P[1]) do
i++
// If P[1] was height maxLevel, we’ll have to search from the beginning
if (i = maxLevel(S))
start ← head(S)
// otherwise, P[i] points at the closest common down node
// on the search paths for current and the element preceding it
else
start ← P[i]
// Now search for current element from start to repopulate the
// part of the Pointer array that differs
SkipListSearch2(S, start, to_return)
// Now P[1] points at the node before the one containing to_return
return to_return
End
Analysis
We need to show that a single call to previous() runs in O(1). There are two parts that might cast doubt on a claim of O(1) complexity - the while loop and the truncated search call.
Proof 1 - Claim: The expected running time of the while loop is a constant as n goes to infinity
The number of times the loop runs is proportional to the number of pointers in the current node. If P[1] is height maxHeight, the test P[i] = P[1] will always be true. But this is vary rare. Remember that the probability of a node having i pointers decreases geometrically with each level, or Pr{ level > i} = p^i. The expected height of a node is equal to the sum of all probability-weighted possible heights. Since the probabilities decrease geometrically and the heights increase linearly, we have an infinitely decreasing geometric series as we let height go to infinity. This, as we all know, is equal to a constant. more formally:
Proof 2 - Claim: The expected running time of SkipListSearch2(S, start, to_current) is constant
A similar analysis as was done for the loop can be applied here. The number of steps performed by SkipListSearch2 is proportional to the height of the P[1] node. If P[1] is short, start will be quite close and the number of steps small. As shown in proof 1, since the probability of a node having i pointers decreases geometrically as i goes to infinity, this leads to an infinitely decreasing geometric series.
An alternative proof would be to just use a corollarly given to us on the assignment handout: The expected number of level i nodes between two nodes that are next to each other at level i + 1 is a constant. We are only ever searching between two nodes of height i+1, and while the probability of height decreases geometrically, the extra steps only increase linearly - namely c * i, one constant weight per level. Again we have an infinitely decreasing geometric series.
Ok, I admit that proof 2 isn’t air tight. But it feels right. And if you actually visualize the algorithm, the search step usually only performs a very, very small number of steps - it is extremely rare that it performs close to the number of steps needed for a full search starting from the head and even this worse case is only O(lgn). It certainly appears to be expected O(1).
I guess I’ll find out when I get my assignment back 
). 
