摘要：從這里我們可以看到，從插入時我們只要保證上一層的元素個數為下一層元素個數的，我們的跳躍表就能成為理想的跳躍表。

總的來說跳躍鏈表最大的好處就是提高了檢索了的速率，可以說說是大幅度的提高，相對于單鏈表來說是一種高效率的檢索結構

跳躍表的結構是：假如底層有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();


    }
}

跳躍鏈表

雙鏈表

單鏈表

java實現跳躍鏈表