今天要介紹一個(gè)這樣的數(shù)據(jù)結(jié)構(gòu)：
單向鏈接
有序保存
支持添加、刪除和檢索操作
鏈表的元素查詢(xún)接近線性時(shí)間
——跳躍表 Skip List
一、普通鏈表
對(duì)于普通鏈接來(lái)說(shuō)，越靠前的節(jié)點(diǎn)檢索的時(shí)間花費(fèi)越低，反之則越高。而且，即使我們引入復(fù)雜算法，其檢索的時(shí)間花費(fèi)依然為O(n)。為了解決長(zhǎng)鏈表結(jié)構(gòu)的檢索問(wèn)題，一位名叫William Pugh的人于1990年提出了跳躍表結(jié)構(gòu)。基本思想是——以空間換時(shí)間。
二、簡(jiǎn)單跳躍表（Integer結(jié)構(gòu)）
跳躍表的結(jié)構(gòu)是多層的，通過(guò)從最高維度的表進(jìn)行檢索再逐漸降低維度從而達(dá)到對(duì)任何元素的檢索接近線性時(shí)間的目的O(logn)。
