跳表
跳表是一种各方面性能都比较优秀的动态数据结构,可以支持快速的插入,删除,查找操作,写起来也不复杂,甚至可以代替红黑树.
如何理解跳表
对于一个单链表来讲,即便存储的数据是有序的,如果我们要在其中查找一个数据,也只能从头到尾遍历链表.这样效率很低,时间复杂度是O(n).
如果我们对链表建立一级索引,我们把抽出来的这一级叫索引或索引层.图中的down表示down指针,指向下一级节点.
//todo 图片9
如果我们现在查找某个结点,比如16.我们先在索引层遍历,当遍历到13的结点时,我们发现下一个结点是17,要查找的结点16肯定在这两个结点之间,然后我们通过索引层的down指针,下降到原始链表这一层,继续遍历.这个时候我们只需要在遍历2个结点,就可以找到16了.这样原来查找16需要遍历10个结点,现在需要遍历7个结点.
加了一层索引后,查找的一个结点需要遍历的结点个数变少了,也就是查询的效率变高了.如果我们在第一集索引的基础之上,每两个结点就抽出一个结点到第二级索引.现在再查找16的话,只需要遍历6个结点.查找的效率又提高了.这种链表加索引的结构,就是跳表
用跳表查询到底有多快?
在多级索引的跳表中,查询某个数据的时间复杂度是O(logn).这个时间复杂度跟二分查找是一样的.这种查找效率的提升,前提是建立了多级索引,也就是空间换时间的设计思路.
跳表是不是浪费内存
比起单纯的链表,跳表需要储存多级索引,肯定要消耗更多的存储空间.跳表的空间复杂度是O(n).
实际上,我们不必太在意索引额外占用的空间.实际开发中,链表存储的可能是很大的对象,而索引只需要存储关键值和几个指针并不需要存储对象.所以当对象比所以结点大很多的时候,那索引占用的额外空间就可以忽略不计了.
高效的动态插入和删除
跳表这个动态数据结构,不仅支持查找操作,还支持动态的插入,删除操作,而且时间复杂度也是O(n).
跳表索引的动态更新
作为一种动态数据结构,我们需要某种手段来维护索引与原始链表大小之间的平衡,也就是说如果链表中结点多了,索引结点就相应的增加一些,避免操作性能下降.
我们通过一个随机函数,来决定将这个结点插入到哪几级索引中.比如随机函数生成了值K,那我们就将这个结点插入到第一级到第K级这K级索引中
//todo 图10