To examine skip list nodes in order, simply chain through the level-0 pointers. For example:void WalkTree(Node *P) { if (P == NIL) return; WalkTree(P->Left); /* examine P->Data here */ WalkTree(P->Right); } WalkTree(Root);
Node *P = List.Hdr->Forward[0]; while (P != NIL) { /* examine P->Data here */ P = P->Forward[0]; }
n = 1 + 1/2 + 1/4 + ... = 2.
method | statements | average time | worst-case time |
---|---|---|---|
hash table | 26 | O(1) | O(n) |
unbalanced tree | 41 | O(lg n) | O(n) |
red-black tree | 120 | O(lg n) | O(lg n) |
skip list | 55 | O(lg n) | O(n) |
method | insert | search | delete |
---|---|---|---|
hash table | 18 | 8 | 10 |
unbalanced tree | 37 | 17 | 26 |
red-black tree | 40 | 16 | 37 |
skip list | 48 | 31 | 35 |
random input | count | hash table | unbalanced tree | red-black tree | skip list |
---|---|---|---|---|---|
16 | 4 | 3 | 2 | 5 | |
256 | 3 | 4 | 4 | 9 | |
4,096 | 3 | 7 | 6 | 12 | |
65,536 | 8 | 17 | 16 | 31 | |
ordered input | 16 | 3 | 4 | 2 | 4 |
256 | 3 | 47 | 4 | 7 | |
4,096 | 3 | 1,033 | 6 | 11 | |
65,536 | 7 | 55,019 | 9 | 15 |