30.11. SkipLists¶
30.11.1. SkipList Idea¶
1 / 18 Settings<<<>>>Here we illustrate the skip list concept. A skip list can be viewed as a sorted linked list with some extra pointers. We start with a simple linked list whose nodes are ordered by key value. To search this list requires that we move down the list one node at a time, visiting O(n) nodes in the average case.
- Hd
Head
- 0
- 5
- 25
- 30
- 31
- 42
- 58
- 62
- 69
- null
30.11.2. SkipList Reality¶
1 / 36 Settings<<<>>>Now we illustrate skip list insertion. The skip list is initialized with a header node of level 0, whose forward pointer is set to null. The top item shows the value associated with the skip list node. The head node is special so, has the value "Hd".
- Hd
Head
- null
30.11.3. Analysis¶
- Best-case behavior is "balanced": Θ(logn) (like a BST).
- Worst-case behavior: All nodes at the same level (regardless of what level): Effectively degenerates to a linked list (like a BST).
- Reality: Its behavior is not so dependent on order of inserts as a BST. Its similar to what BST cost would be if we randomized the input order. A huge improvement in expected performance!
30.11.4. Programming Principles¶
- All container classes should be general.
- Any container class's initial state should be identical to its empty state.
