5、总结
在数据规模比较小时,跳跃表形成后可能不是理想的跳跃表结构,但是当数据量增大,结构越接近理想的跳跃表结构。
bw指针不是所有的语言的实现都存在,这个是参考了Redis的跳跃表实现,笔者自己加上去的。
跳跃表不同于树结构,如红黑树等,它不需要花费过多的精力进行平衡算法,这也是跳跃表的性能优越的一个方面。
跳跃表结构是拿空间换时间的一种结构,尽管空间占用不是很大。
查询、删除,平均时间复杂度都是O(logn),而插入的平均时间复杂度也是O(logn) 因为涉及到增层操作,所以这里需要注意不是O(n).
此博客为笔者参考网络上各类文章总结性书写,原创手打,如有错误欢迎指正。