# 跳跃列表

算法 空间 平均 最差 O(n) O(n log n)[1] O(log n) O(n)[1] O(log n) O(n) O(log n) O(n)

## 描述

### 实现细节

${\displaystyle {\mathcal {O}}(n)}$ 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 ${\displaystyle {\mathcal {O}}(\log n)}$ search time. (Choose the level of the i'th finite node to be 1 plus the number of times we can repeatedly divide i by 2 before it becomes odd. Also, i=0 for the negative infinity header as we have 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.

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
if i is not the last node at level j
randomly choose whether to promote it to level j+1
else
do not promote
end if
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


## 参考文献

1. Papadakis, Thomas. Skip Lists and Probabilistic Analysis of Algorithms (PDF) (Ph.D.). University of Waterloo. 1993.
2. ^ Pugh, W. Skip lists: A probabilistic alternative to balanced trees (PDF). Communications of the ACM. 1990, 33 (6): 668. doi:10.1145/78973.78977.
3. ^ Munro, J. Ian; Papadakis, Thomas; Sedgewick, Robert. Deterministic skip lists (PDF). Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms (SODA '92). Orlando, Florida, USA: Society for Industrial and Applied Mathematics, Philadelphia, PA, USA: 367–375. 1992. doi:10.1145/139404.139478.