possible to trade search costs against storage costs. Implementation details The elements used for a skip list can contain more than one pointer since they can participate in more than one list. Insertions and deletions are implemented much like the corresponding linked-list operations, except that "tall" elements must be inserted into or deleted from more than one linked list. operations, which force us to visit every node in ascending order (such as printing the entire list), provide the opportunity to perform a behind-the-scenes derandomization of the level structure of the skip-list in an optimal way, bringing the skip list to search time. (Choose the level of the i'th finite node to be 1 plus the number of times it is possible to repeatedly divide i by 2 before it becomes odd. Also, i=0 for the negative infinity header as there is the usual special case of choosing the highest possible level for negative and/or positive infinite nodes.) However this also allows someone to know where all of the higher-than-level 1 nodes are and delete them. Alternatively, the level structure could be made quasi-random in the following way: make all nodes level 1 j ← 1 while the number of nodes at level j > 1 do for each i'th node at level j do if i is odd and i is not the last node at level j randomly choose whether to promote it to level j+1 else if i is even and node i-1 was not promoted promote it to level j+1 end if repeat j ← j + 1 repeat Like the derandomized version, quasi-randomization is only done when there is some other reason to be running an operation (which visits every node). The advantage of this quasi-randomness is that it doesn't give away nearly as much level-structure related information to an adversarial user as the de-randomized one. This is desirable because an adversarial user who is able to tell which nodes are not at the lowest level can pessimize performance by simply deleting higher-level nodes. (Bethea and Reiter however argue that nonetheless an adversary can use probabilistic and timing methods to force performance degradation.) The search performance is still guaranteed to be logarithmic. It would be tempting to make the following "optimization": In the part which says "Next, for each ith...", forget about doing a coin-flip for each even-odd pair. Just flip a coin once to decide