跳躍列表

跳躍列表
類型	列表
發明時間	1989
發明者	W. Pugh
用大O符號表示的時間複雜度
算法 平均 最差 空間 O(n) O(n log n) 搜尋 O(log n) O(n) 插入 O(log n) O(n) 刪除 O(log n) O(n)

在計算機科學中，跳躍列表是一種數據結構。它使得包含n個元素的有序序列的查找和插入操作的平均時間複雜度都是$O(\log n)$，優於數組的$O(n)$複雜度。

快速的查詢效果是通過維護一個多層次的鍊表實現的，且與前一層（下面一層）鍊表元素的數量相比，每一層鍊表中的元素的數量更少（見右下角示意圖）。一開始時，算法在最稀疏的層次進行搜索，直至需要查找的元素在該層兩個相鄰的元素中間。這時，算法將跳轉到下一個層次，重複剛才的搜索，直到找到需要查找的元素為止。跳過的元素的方法可以是隨機性選擇或確定性選擇，其中前者更為常見。

描述

一張跳躍列表的示意圖。每個帶有箭頭的框表示一個指針, 而每行是一個稀疏子序列的鍊表；底部的編號框（黃色）表示有序的數據序列。查找從頂部最稀疏的子序列向下進行, 直至需要查找的元素在該層兩個相鄰的元素中間。

跳躍列表是按層建造的。底層是一個普通的有序鍊表。每個更高層都充當下面列表的「快速通道」，這裡在第$i$層中的元素按某個固定的概率$p$（通常為${\frac {1}{2}}$或${\frac {1}{4}}$）出現在第$i+1$ 層中。每個元素平均出現在${\frac {1}{1-p}}$個列表中，而最高層的元素（通常是在跳躍列表前端的一個特殊的頭元素）在$\log _{1/p}n$個列表中出現。

在查找目標元素時，從頂層列表、頭元素起步。算法沿着每層鍊表搜索，直至找到一個大於或等於目標的元素，或者到達當前層列表末尾。如果該元素等於目標元素，則表明該元素已被找到；如果該元素大於目標元素或已到達鍊表末尾，則退回到當前層的上一個元素，然後轉入下一層進行搜索。每層鍊表中預期的查找步數最多為${\frac {1}{p}}$，而層數為$\log _{1/p}n$，所以查找的總體步數為$-{\frac {\log _{p}n}{p}}$，由於$p$是常數，查找操作總體的時間複雜度為${\mathcal {O}}(\log n)\,$。而通過選擇不同$p$值，就可以在查找代價和存儲代價之間取得平衡。

跳躍列表不像平衡樹等數據結構那樣提供對最壞情況的性能保證：由於用來建造跳躍列表採用隨機選取元素進入更高層的方法，在小概率情況下會生成一個不平衡的跳躍列表（最壞情況例如最底層僅有一個元素進入了更高層，此時跳躍列表的查找與普通列表一致）。但是在實際中它通常工作良好，隨機化平衡方案也比平衡二叉查找樹等數據結構中使用的確定性平衡方案容易實現。跳躍列表在並行計算中也很有用：插入可以在跳躍列表不同的部分並行地進行，而不用對數據結構進行全局的重新平衡。

實現細節

往跳躍列表中插入一個元素

因為跳躍列表中的元素可以在多個列表中，所以每個元素可以有多於一個指針。

跳躍列表的插入和刪除的實現與普通的鍊表操作類似，但高層元素必須在進行多個鍊表中進行插入或刪除。

跳躍列表的最壞時間性能具有一定隨機性，但是可以通過時間複雜度為${\mathcal {O}}(n)$的遍歷操作（例如在打印列表全部內容時）以無隨機的算法重整列表的結構，從而使跳躍列表的實際查找時間複雜度儘量符合理論平均值${\mathcal {O}}(\log n)$。

除了使用無隨機算法之外，我們可以以下面的准隨機方式地生成每一層：

make all nodes level 1
j ← 1
while the number of nodes at level j > 1 do
  for each i'th node at level j do
    if i is odd 
      if i is not the last node at level j
        randomly choose whether to promote it to level j+1
      else
        do not promote
      end if
    else if i is even and node i-1 was not promoted
      promote it to level j+1
    end if
  repeat
  j ← j + 1
repeat

類似無隨機版本，准隨機重整僅在需要執行一個${\mathcal {O}}(n)$操作（訪問每個節點）的時候伴隨進行。

歷史

跳躍列表由威廉·普發明。發明者對跳躍列表的評價是：「跳躍列表是在很多應用中有可能替代平衡樹而作為實現方法的一種數據結構。跳躍列表的算法有同平衡樹一樣的漸進的預期時間邊界，並且更簡單、更快速和使用更少的空間。」

參見

• 布隆過濾器
• 跳躍圖

外部連結

• Description （頁面存檔備份，存於網際網路檔案館） from the Dictionary of Algorithms and Data Structures
• skip lists by Thomas Niemann
• Skip List（跳躍表）原理詳解與實現 - One thing I know,that is I know nothing.(Socrates Greek) - ITeye技術網站 （頁面存檔備份，存於網際網路檔案館）