【数据结构】跳表

SkipList(跳表)这种数据结构是由William Pugh于1990年在在 Communications of the ACM June 1990, 33(6) 668-676 发表了Skip lists: a probabilistic alternative to balanced trees

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LdKnTveo-1660144872412)(…/…/…/…/blogimgv2022/v2-e03110ee7d29ec51d1c98ea628914c21_720w.jpg)]

原理及实现

其实跳表就是在普通单向链表的基础上增加了一些索引，而且这些索引是分层的，从而可以快速地查的到数据。单向链表就是最初存储所有数据的线性链表

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yPLIatrs-1660144872416)(…/…/…/…/blogimgv2022/image-20220810213424066.png)]

Node节点结构

//Class template to implement node
template<typename K, typename V>
1