PineWikiA skip list is a randomized tree-like data structure based on linked lists. It consists of a level 0 list that is an ordinary sorted linked list, together with higher-level lists that contain a random sampling of the elements at lower levels. When inserted into the level i list, an element flips a coin that tells it with probability p to insert itself in the level i+1 list as well.
Searches in a skip list are done by starting in the highest-level list and searching forward for the last element whose key is smaller than the target; the search then continues in the same way on the next level down. To bound the expected running time of a search, it helps to look at this process backwards; the reversed search path starts at level 0 and continues going backwards until it reaches the first element that is also in a higher level; it then jump to the next level up and repeats the process. Because each new node encountered on a particular level has probability p of being on the next level up, the reversed search touches an expected 1/p elements at each level. On average, there will be about log1/p n levels, so the total cost is O((1/p) log1/p n) = O(log n) when p is constant. By adjusting p up or down we can decrease or increase the constant factor on this time.
The space per element of a skip list also depends on p. Every element has at least one outgoing pointer (on level 0), and on average has exactly 1/(1-p) expected pointers. So the space cost can also be adjusted by adjusting p. For example, if space is at a premium, setting p = 1/10 produces 10/9 pointers per node on average---not much more than in a linked list---but still gives O(log n) search times.
1. More about skip lists
The original skip list paper, published by William Pugh in Communications of the ACM in 1990, can be found at ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf.
A Java applet that demonstrates skip lists can be found at http://iamwww.unibe.ch/~wenger/DA/SkipList/.