對于一個有序數組，如果要查找其中的一個數，我們可以使用二分查找(Binary Search)算法，将它的時間複雜度降低為O(logn).那查找一個有序連結清單，有沒有辦法将其時間複雜度也降低為O(logn)呢？
跳表(skip list),全稱為跳躍連結清單，實質上就是一種可以進行二分查找的有序連結清單，它允許快速查詢、插入和删除有序連結清單。
跳表使用的前提是連結清單有序，就像二分查找也要求有序數組
怎麼了解跳表
比如我們有一個原始有序連結清單，如下圖所示。
要查找其中值為20的元素，之前都是采取按順序進行周遊的方法，但這樣做時間複雜度就變成了O(n).怎樣才能提高效率呢？我們可以通過對連結清單建立一級索引，查找的時候先周遊索引，通過索引找到原始層繼續周遊。索引如下圖所示
那麼查找20的過程就變成了先使用索引周遊 2 -> 7 -> 12 -> 20，然後順着索引連結清單的結點向下找到原始連結清單的結點20.之前需要周遊7次，現在需要周遊5次。在資料量小的時候跳表性能優化并不明顯，但當有序連結清單包含大量資料時，結點的通路次數大緻會減少一半。
現在我們添加兩層索引，基于第一層的索引再添加一層，如下圖所示
要查找20，先在第二層索引上周遊 2 -> 12 ,然後向下轉到第一層索引周遊 12 - > 20，最後向下找到原始連結清單的結點20.
這個例子中，原始有序連結清單的結點數量很少，當結點數量很多時，可以抽出更多的索引層級，每一層索引結點的數量都是低層索引的一半。
跳表複雜度分析
時間複雜度
算法的執行效率可以通過時間複雜度來衡量，跳表的時間複雜度是多少呢？我們來分析一下。
前面我們每兩個結點抽一個結點作為上一級索引的結點，那麼假設原始連結清單的長度為n，第一層索引的結點個數為n/2,第二層索引的個數為n/4,第k級的索引結點個數就是n/(2k)。假設索引有 h 級，最進階的索引有 2 個結點。通過上面的公式，我們可以得到 n/(2h)=2，進而求得 h=log2n-1。如果包含原始連結清單這一層，整個跳表的高度就是 log2n。我們在跳表中查詢某個資料的時候，如果每一層都要周遊 m 個結點，那在跳表中查詢一個資料的時間複雜度就是 O(m*logn)。
m的值怎麼計算呢？在上面的例子中，每一層最多隻需要周遊三個元素，是以m=3，根據時間複雜度的計算規則，高階的常數項也可以省略，是以跳表中查詢任意資料的時間複雜度就是
O(logn)
空間複雜度
每兩個結點中抽一個結點作為上級索引，很明顯，它的空間複雜度為
O(n)
.