# 跳跃列表

算法 空间 平均 最差 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) (学位论文). University of Waterloo. 1993 [2018-06-03]. （原始内容 (PDF)存档于2017-08-10）.
2. Pugh, W. Skip lists: A probabilistic alternative to balanced trees (PDF). Communications of the ACM. 1990, 33 (6): 668 [2018-06-03]. doi:10.1145/78973.78977. （原始内容存档 (PDF)于2020-06-20）.
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 [2018-06-03]. doi:10.1145/139404.139478. （原始内容 (PDF)存档于2021-05-06）.