基本介紹
簡介,描述,實現細節,歷史,參見,
簡介
在計算機科學領域，跳躍鍊表是一種數據結構，允許快速查詢一個有序連續元素的數據鍊表。快速查詢是通過維護一個多層次的鍊表，且每一層鍊表中的元素是前一層鍊表元素的子集（見右邊的示意圖）。一開始時，算法在最稀疏的層次進行搜尋，直至需要查找的元素在該層兩個相鄰的元素中間。這時，算法將跳轉到下一個層次，重複剛才的搜尋，直到找到需要查找的元素為止。被挑過的元素可能被隨機性地選擇或確定性地選擇，其中前者更為常見。
描述
跳躍列表是按層建造的。底層是一個普通的有序鍊表。每個更高層都充當下面列表的“快速跑道”，這裡在第i層中的元素按某個固定的機率p（通常為1/2或1/4）出現在第i+1層中。平均起來，每個元素都在
個列表中出現，而最高層的元素（通常是在跳躍列表前端的一個特殊的頭元素）在
(即基於1/p的n的對數）個列表中出現。
要查找一個目標元素，起步於頭元素和頂層列表，並沿著每個鍊表搜尋，直到到達小於或著等於目標的最後一個元素。通過跟蹤起自目標直到到達在更高列表中出現的元素的反向查找路徑，在每個鍊表中預期的步數顯而易見最多為1/p。所以查找的總體代價是
，當p是常數時是
。通過選擇不同p值，就可以在查找代價和存儲代價之間作出權衡。
插入和刪除的實現非常像相應的鍊表操作，除了"高層"元素必須在多個鍊表中插入或刪除之外。
跳躍列表不像某些傳統平衡樹數據結構那樣提供絕對的最壞情況性能保證，因為用來建造跳躍列表的扔硬幣方法總有可能（儘管機率很小）生成一個糟糕的不平衡結構。但是在實際中它工作的很好，隨機化平衡方案比在平衡二叉查找樹中用的確定性平衡方案容易實現。跳躍列表在並行計算中也很有用，這裡的插入可以在跳躍列表不同的部分並行的進行，而不用全局的數據結構重新平衡。
實現細節
我們可以以下面的方式準隨機地生成每一層：
make all nodes level 1j ← 1while 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 + 1repeat
近似於無隨機版本，準隨機僅在需要運行一個{\displaystyle {\mathcal {O}}(n)}操作（訪問每個節點）的時候進行。
歷史
跳躍列表由William Pugh發明。他在Communications of the ACMJune 1990, 33(6) 668-676 發表了Skip lists: a probabilistic alternative to balanced trees，在其中詳細描述了他的工作。
引用發明者的話：
跳躍列表是在很多套用中有可能替代平衡樹而作為實現方法的一種數據結構。跳躍列表的算法有同平衡樹一樣的漸進的預期時間邊界，並且更簡單、更快速和使用更少的空間。
參見
- 跳躍圖
