跳表SkipList的原理和C实现
跳表SkipList,顾名思义是链表的一种,或者说它是单链表的变异实现,使用跳表可以将查询操作的复杂度控制到θ(lg N),而普通的链表只能通过顺序查找,复杂度为θ(N),如此跳表的优势就很明显了,虽然它是通过以空间换时间搞定的。
先看一下普通的有序单链表:
要在里面查找一个值就需要顺序比较,复杂度大家都清楚了。...
a Linux kernel virtualization developer, the contributor to KVM/Xen community, expert in VT-x, VT-d and X86 architecture, familiar with kernel development in KVM, XEN, Filesystem, IO storage, memory, schedule, etc.