# 跳跃列表

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

## 描述

### 实现细节

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.