[TOC] # 簡介 總的來說跳躍鏈表最大的好處就是提高了檢索了的速率， 可以說說是大幅度的提高，相對于單鏈表來說是一種高效率的檢索結構 # 原理 跳躍表的結構是：假如底層有10個節點， 那么底層的上一層理論上就有5個節點， 再上一層理論上就有2個或3個節點， 再上一層理論上就有1個節點。 所以從這里可以看出每一層的節點個數為其下一層的1/2個元素，以此類推。 從這里我們可以看到，從插入時我們只要保證上一層的元素個數為下一層元素個數的1/2，我們的跳躍表就能成為理想的跳躍表。 那么怎么才能保證我們插入時上層元素個數是下層元素個數的1/2呢，？ 很簡單 拋硬幣就可以解決了， 假設元素X要插入跳躍表，最底層是肯定要插入X的， 那么次低層要不要插入呢，我們希望上層元素個數是下層的1/2， 那么我們有1/2的概率要插入到次低層， 這樣就來拋硬幣吧，正面就插入，反面就不插入，次次底層相對于次低層， 我們還是有1/2的概率插入，那么就繼續拋硬幣吧 ， 以此類推元，素X插入第n層的概率是(1/2)的n次。 這樣，我們能在跳躍表中插入一個元素了。基本的樣子如下圖：  # 代碼實現 ## 節點定義 ~~~ package skip; public class Node { public Integer value; //插入的數據 public Node left; //分別對應的四個方向的指針 public Node down; public Node right; public Node up; public Node(Integer value) //構造函數 { this.value=value; down=up=right=left=null; } } ~~~ ## 表的實現 ~~~ package skip; import java.util.Random; public class SkipList { private Node head; //最上面一側的頭結點，這里使用的是雙鏈表 private Node tail; //最上面一層的尾節點，這里的頭尾節點是不存儲數據的，數據域全是null private int level; //表中的最高的層數，就是總共的層數 private int size; //插入節點的個數，頭尾節點除外 private Random random; //用來判斷是否需要增加高度的隨機函數 public SkipList() { level = 0; //level默認是0層，就是只有最下面的一層 head = new Node(null); tail = new Node(null); head.right = tail; //這里初始化成一個只有一層的雙鏈表 tail.left = head; size = 0; //size初始化為0 random = new Random(); } //這個函數的作用是找到插入節點的前面一個節點，這里默認的是將表升序存儲 public Node findFirst(Integer value) { Node p = head; while (true) { //判斷要插入的位置，當沒有查到尾節點并且要插入的數據還是比前面的大的話，就將節點右移，知道找到合適的位置 //這里需要注意的是這里的head代表不一定是最底層的，因此這里的查找都是從最高層進行查找的，如果滿足條件就要向下移動 //直到最底層 while (p.right.value != null && p.right.value <= value) { p = p.right; } //向下移動，直到到達最后一層 if (p.down != null) { p = p.down; } else { //到達最底層跳出即可 break; } } return p; //此時這里的p就是要插入節點的前面一個節點 } //這是插入函數，這里先執行插入，然后判斷是否需要增加高度 public void insert(int value) { Node curr = findFirst(value); //先找到插入位置的前面一個節點 Node q = new Node(value); //新建一個插入的節點 //下面執行插入步驟，這個和雙鏈表是一樣的步驟 q.right = curr.right; q.left = curr; curr.right.left = q; curr.right = q; int i = 0; //表示當前節點所在的層數，開始插入的是在下面插入的，所以開始的時候是在0層 //這里判斷是否需要增加高度，每一層相對域下面來說都有二分之一的概率，也就是說每一層增加的概率是（1/2）^n //通俗的說就是每一層的節點是將會保證是下面一層的1/2 while (random.nextDouble() < 0.5) { if (i >= level) { //如果當前插入的節點所處的層數大于等于最大的層數，那么就需要增加高度了，因為這里要保證頭尾節點的高度是最高的 //下面的代碼就是在頭尾節點的上插入新的節點，以此來增加高度 Node p1 = new Node(null); Node p2 = new Node(null); p1.right = p2; p1.down = head; p2.left = p1; p2.down = tail; head.up = p1; //將頭尾節點上移，成為最頂層的節點，這就是為什么每次插入和查詢的時候都是最上面開始查詢的，因為這里的head默認的就是從最上面開始的 tail.up = p2; head = p1; tail = p2; level++; //最高層數加一 } while (curr.up == null) { //當然增加高度就是在插入節點上面新插入一個節點，然后將之與插入的節點相連 //既然這里新插入節點增高了，那么就需要找到與新插入節點上面的那個節點相連接，這里我們將新插入節點的前面的同等高度的節點與之相連 curr = curr.left; } curr = curr.up; //通過前面的一個節點找到與之相連的節點 //下面就是創建一個節點插入到插入節點的頭上以此來增加高度，并且這個節點與前面一樣高的節點相連 Node e = new Node(value); e.left = curr; e.right = curr.right; curr.right.left = e; //此時的curr就是與之同等高度的節點 curr.right = e; e.down = q; q.up = e; q = e; //將新插入的節點上移到最上面，因為后面可能還要在這里增加高度，就是在最上面插入新的一模一樣的節點 i++; //增加當前所處的高度，這里一定能要記得寫上，如果還要繼續增加的話，需要判讀是否需要增加頭尾節的高度 } size++; //節點加一 } //下面是打印每一層節點的情況 public void display() { while (level >= 0) { Node p = head; while (p != null) { System.out.print(p.value + "-------->"); p = p.right; } System.out.println(); System.out.println("*****************************"); level--; head = head.down; } } /*在鏈表中查找某個值是否存在，如果存在找到的節點，當然先從最高層開始查找，如果找到了在比這個值小的最后一個值，那么就順著這個值的下面開始尋找，按照上面的步驟 再次尋找，如過這個值正好等于要找的值，就返回true，形象的來說就是形成一個梯度的感覺。注意這里返回的節點一定是最底層的節點，利于下面的刪除操作 * */ public Node search(int value) { Node p = head; while (true) { /*這里一定要寫成p.right.value!=null,如果寫成p.right!=null運行可能有錯誤， 因為這里的尾節點的值為null，但是它的節點不是空的，如果成這樣的話,那么節點可能會找到尾節點都沒有找到，此時在判斷value的值就出現錯誤 相當與判斷tail.right.value<=value,這個肯定是不行的，因為這個節點不存在，是空的更別說值了 */ //從最高層開始判斷找到比這個小的最后一個值，就是找到一個節點的前面比value小的，后面的節點的值比value大的 while (p.right.value != null && p.right.value <= value) { p = p.right; //如果沒有找到就后移直到找到這個節點 } //如果找到的這個節點不是最底層的話，就向下移動一層，然后循環再次尋找，總之就是從最高層開始，一層一層的尋找 if (p.down != null) { //這個表示上面的循環沒有找到的相等的，那么就向下移動一層 p = p.down; } else { //如果到了最底層了，這里的值仍然沒有找到這個值，那么就表示不存在這個值 if (p.value == value) { //判斷是否存在value相等的值 // System.out.println(p.value + "----->"); return p; //返回節點 } return null; //仍然沒有找到返回null } } } /* 這里是利用上面的查找函數，找到當前需要刪除的節點，當然這個節點是最底層的節點，然后循環從最底層開始刪除所有的節點 * */ public void delete(int value) { Node temp = search(value); //這里返回的必須是最底層的節點，因為要從最下面的往上面全部刪除所有層的節點，否則的話可能在某一層上仍然存在這個節點 while (temp != null) { temp.left.right = temp.right; temp.right.left = temp.left; temp = temp.up; //節點上移，繼續刪除上一層的節點 } } public static void main(String args[]) { SkipList skipList = new SkipList(); Random random = new Random(); skipList.insert(33); skipList.insert(44); skipList.insert(11); skipList.insert(10); skipList.insert(22); skipList.insert(22); for (int i = 0; i < 500; i++) { int value = (int) (random.nextDouble() * 1000); skipList.insert(value); // System.out.println(value); } Node p = skipList.search(22); if (p != null) { System.out.println(p.value); } else System.out.println("沒有找到"); skipList.delete(33); skipList.display(); } } ~~~