什么是跳表
跳表是一種有序的數(shù)據(jù)結構，它通過在每個節(jié)點中維持多個指向其它節(jié)點的指針辽剧，從而達到快速訪問的目的。
核心思想
這是一個單向鏈表税产，我們要查詢鏈表中某個元素的話怕轿，需要遍歷整條鏈，所以鏈表查詢的時間復雜度為O(N)辟拷。
O(N)撞羽，這個時間復雜度比較高，查詢效率較低衫冻，于是就有人試圖優(yōu)化诀紊。
其中，William Pugh 受到二分查找的啟發(fā)隅俘，就思考能不能通過二分法來跳過部分節(jié)點邻奠，直接鎖定目標笤喳。于是，他做出了這樣的假設碌宴。
如果是說鏈表是排序的杀狡，并且節(jié)點中還存儲了指向前面第二個節(jié)點的指針的話，那么在查找一個節(jié)點時贰镣，僅僅需要遍歷N/2個節(jié)點即可呜象。
同理，如果節(jié)點中還存儲指向前面第四個節(jié)點的指針的話碑隆，那么查找下一個節(jié)點時恭陡，僅僅需要遍歷N/4個節(jié)點。
這就是跳表的核心思想上煤，通過一個“空間來換取時間”的算法休玩，通過在每個節(jié)點中增加了向前的指針，從而提升查找的效率劫狠，顯然哥捕，它的查找時間復雜度為O(logN)。
其實嘉熊，這只是理想狀態(tài)下的跳表。
在這種理想狀態(tài)下扬舒，每次插入或者刪除節(jié)點時阐肤，新節(jié)點前面的所有節(jié)點都要重新關聯(lián)，這顯然不是我們想要的結果讲坎。
現(xiàn)實中的跳表是這樣的孕惜。
跳表的性質
(1) 由很多層結構組成
(2) 每一層都是一個有序的鏈表
(3) 最底層(Level 1)的鏈表包含所有元素
(4) 如果一個元素出現(xiàn)在 Level i 的鏈表中，則它在 Level i 之下的鏈表也都會出現(xiàn)晨炕。
跳表的結構
跳躍表的節(jié)點有三部分構成：key值衫画，value值，以及指向前向節(jié)點的指針數(shù)組瓮栗，指針數(shù)組的大小由該節(jié)點的層數(shù)決定削罩。
所以，節(jié)點的數(shù)據(jù)類型可以定義為
typedef struct nodeStructure {
keyType key; // key值
valueType value; // value值
node forward[1]; // 向前指針數(shù)組费奸，根據(jù)該節(jié)點層數(shù)的不同指向不同大小的數(shù)組
};
定義跳表數(shù)據(jù)類型：
typedef struct listStructure {
int level; // 跳表的層數(shù)
struct nodeStructure * header; // 指向header節(jié)點的指針
} * list;
跳表的操作
查詢
對于下圖這個鏈表結構弥激，假設我們要查詢值為56的節(jié)點，我們需要比較10次愿阐。
使用跳表優(yōu)化過的查詢算法微服，我們只需要比較3次。
插入
同鏈表類似缨历。
刪除
同鏈表類似以蕴。
性能對比
我們對跳躍表糙麦、平衡樹等進行比較，如下圖()所示：
