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

總的來(lái)說(shuō)跳躍鏈表最大的好處就是提高了檢索了的速率，可以說(shuō)說(shuō)是大幅度的提高，相對(duì)于單鏈表來(lái)說(shuō)是一種高效率的檢索結(jié)構(gòu)

跳躍表的結(jié)構(gòu)是：假如底層有10個(gè)節(jié)點(diǎn)， 那么底層的上一層理論上就有5個(gè)節(jié)點(diǎn)，再上一層理論上就有2個(gè)或3個(gè)節(jié)點(diǎn)，再上一層理論上就有1個(gè)節(jié)點(diǎn)。所以從這里可以看出每一層的節(jié)點(diǎn)個(gè)數(shù)為其下一層的1/2個(gè)元素，以此類(lèi)推。從這里我們可以看到，從插入時(shí)我們只要保證上一層的元素個(gè)數(shù)為下一層元素個(gè)數(shù)的1/2，我們的跳躍表就能成為理想的跳躍表。那么怎么才能保證我們插入時(shí)上層元素個(gè)數(shù)是下層元素個(gè)數(shù)的1/2呢，？很簡(jiǎn)單 拋硬幣就可以解決了，假設(shè)元素X要插入跳躍表，最底層是肯定要插入X的，那么次低層要不要插入呢，我們希望上層元素個(gè)數(shù)是下層的1/2，那么我們有1/2的概率要插入到次低層，這樣就來(lái)拋硬幣吧，正面就插入，反面就不插入，次次底層相對(duì)于次低層，我們還是有1/2的概率插入，那么就繼續(xù)拋硬幣吧 ， 以此類(lèi)推元，素X插入第n層的概率是(1/2)的n次。這樣，我們能在跳躍表中插入一個(gè)元素了。基本的樣子如下圖：

package skip;

public class Node
{
    public Integer value;    //插入的數(shù)據(jù)
    public Node left;     //分別對(duì)應(yīng)的四個(gè)方向的指針
    public Node down;
    public Node right;
    public Node up;
    public Node(Integer value)   //構(gòu)造函數(shù)
    {
        this.value=value;
        down=up=right=left=null;
    }
}

package skip;
import java.util.Random;

public class SkipList {
    private Node head;   //最上面一側(cè)的頭結(jié)點(diǎn)，這里使用的是雙鏈表
    private Node tail;   //最上面一層的尾節(jié)點(diǎn)，這里的頭尾節(jié)點(diǎn)是不存儲(chǔ)數(shù)據(jù)的，數(shù)據(jù)域全是null
    private int level;    //表中的最高的層數(shù)，就是總共的層數(shù)
    private int size;    //插入節(jié)點(diǎn)的個(gè)數(shù)，頭尾節(jié)點(diǎn)除外
    private Random random;   //用來(lái)判斷是否需要增加高度的隨機(jī)函數(shù)

    public SkipList() {
        level = 0;     //level默認(rèn)是0層，就是只有最下面的一層
        head = new Node(null);
        tail = new Node(null);
        head.right = tail;    //這里初始化成一個(gè)只有一層的雙鏈表
        tail.left = head;
        size = 0;     //size初始化為0
        random = new Random();
    }

    //這個(gè)函數(shù)的作用是找到插入節(jié)點(diǎn)的前面一個(gè)節(jié)點(diǎn)，這里默認(rèn)的是將表升序存儲(chǔ)
    public Node findFirst(Integer value) {
        Node p = head;
        while (true) {
            //判斷要插入的位置，當(dāng)沒(méi)有查到尾節(jié)點(diǎn)并且要插入的數(shù)據(jù)還是比前面的大的話(huà)，就將節(jié)點(diǎn)右移，知道找到合適的位置
            //這里需要注意的是這里的head代表不一定是最底層的，因此這里的查找都是從最高層進(jìn)行查找的，如果滿(mǎn)足條件就要向下移動(dòng)
            //直到最底層
            while (p.right.value != null && p.right.value <= value) {
                p = p.right;
            }

            //向下移動(dòng)，直到到達(dá)最后一層
            if (p.down != null) {
                p = p.down;
            } else {   //到達(dá)最底層跳出即可
                break;
            }
        }
        return p;  //此時(shí)這里的p就是要插入節(jié)點(diǎn)的前面一個(gè)節(jié)點(diǎn)
    }

    //這是插入函數(shù)，這里先執(zhí)行插入，然后判斷是否需要增加高度
    public void insert(int value) {
        Node curr = findFirst(value);  //先找到插入位置的前面一個(gè)節(jié)點(diǎn)

        Node q = new Node(value);   //新建一個(gè)插入的節(jié)點(diǎn)

        //下面執(zhí)行插入步驟，這個(gè)和雙鏈表是一樣的步驟
        q.right = curr.right;
        q.left = curr;
        curr.right.left = q;
        curr.right = q;

        int i = 0;   //表示當(dāng)前節(jié)點(diǎn)所在的層數(shù)，開(kāi)始插入的是在下面插入的，所以開(kāi)始的時(shí)候是在0層

        //這里判斷是否需要增加高度，每一層相對(duì)域下面來(lái)說(shuō)都有二分之一的概率，也就是說(shuō)每一層增加的概率是（1/2）^n
        //通俗的說(shuō)就是每一層的節(jié)點(diǎn)是將會(huì)保證是下面一層的1/2
        while (random.nextDouble() < 0.5) {
            if (i >= level) {   //如果當(dāng)前插入的節(jié)點(diǎn)所處的層數(shù)大于等于最大的層數(shù)，那么就需要增加高度了，因?yàn)檫@里要保證頭尾節(jié)點(diǎn)的高度是最高的

                //下面的代碼就是在頭尾節(jié)點(diǎn)的上插入新的節(jié)點(diǎn)，以此來(lái)增加高度
                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;    //將頭尾節(jié)點(diǎn)上移，成為最頂層的節(jié)點(diǎn)，這就是為什么每次插入和查詢(xún)的時(shí)候都是最上面開(kāi)始查詢(xún)的，因?yàn)檫@里的head默認(rèn)的就是從最上面開(kāi)始的
                tail.up = p2;

                head = p1;
                tail = p2;
                level++;    //最高層數(shù)加一
            }

            while (curr.up == null) {    //當(dāng)然增加高度就是在插入節(jié)點(diǎn)上面新插入一個(gè)節(jié)點(diǎn)，然后將之與插入的節(jié)點(diǎn)相連
                //既然這里新插入節(jié)點(diǎn)增高了，那么就需要找到與新插入節(jié)點(diǎn)上面的那個(gè)節(jié)點(diǎn)相連接，這里我們將新插入節(jié)點(diǎn)的前面的同等高度的節(jié)點(diǎn)與之相連
                curr = curr.left;
            }

            curr = curr.up;    //通過(guò)前面的一個(gè)節(jié)點(diǎn)找到與之相連的節(jié)點(diǎn)


            //下面就是創(chuàng)建一個(gè)節(jié)點(diǎn)插入到插入節(jié)點(diǎn)的頭上以此來(lái)增加高度，并且這個(gè)節(jié)點(diǎn)與前面一樣高的節(jié)點(diǎn)相連
            Node e = new Node(value);
            e.left = curr;
            e.right = curr.right;
            curr.right.left = e;    //此時(shí)的curr就是與之同等高度的節(jié)點(diǎn)
            curr.right = e;
            e.down = q;
            q.up = e;

            q = e;   //將新插入的節(jié)點(diǎn)上移到最上面，因?yàn)楹竺婵赡苓€要在這里增加高度，就是在最上面插入新的一模一樣的節(jié)點(diǎn)

            i++;   //增加當(dāng)前所處的高度，這里一定能要記得寫(xiě)上，如果還要繼續(xù)增加的話(huà)，需要判讀是否需要增加頭尾節(jié)的高度
        }
        size++;   //節(jié)點(diǎn)加一
    }


    //下面是打印每一層節(jié)點(diǎn)的情況
    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;

        }
    }


    /*在鏈表中查找某個(gè)值是否存在，如果存在找到的節(jié)點(diǎn)，當(dāng)然先從最高層開(kāi)始查找，如果找到了在比這個(gè)值小的最后一個(gè)值，那么就順著這個(gè)值的下面開(kāi)始尋找，按照上面的步驟
    再次尋找，如過(guò)這個(gè)值正好等于要找的值，就返回true，形象的來(lái)說(shuō)就是形成一個(gè)梯度的感覺(jué)。注意這里返回的節(jié)點(diǎn)一定是最底層的節(jié)點(diǎn)，利于下面的刪除操作
    * */
    public Node search(int value) {
        Node p = head;
        while (true) {

            /*這里一定要寫(xiě)成p.right.value!=null,如果寫(xiě)成p.right!=null運(yùn)行可能有錯(cuò)誤，
            因?yàn)檫@里的尾節(jié)點(diǎn)的值為null，但是它的節(jié)點(diǎn)不是空的，如果成這樣的話(huà),那么節(jié)點(diǎn)可能會(huì)找到尾節(jié)點(diǎn)都沒(méi)有找到，此時(shí)在判斷value的值就出現(xiàn)錯(cuò)誤
            相當(dāng)與判斷tail.right.value<=value,這個(gè)肯定是不行的，因?yàn)檫@個(gè)節(jié)點(diǎn)不存在，是空的更別說(shuō)值了
            */

            //從最高層開(kāi)始判斷找到比這個(gè)小的最后一個(gè)值，就是找到一個(gè)節(jié)點(diǎn)的前面比value小的，后面的節(jié)點(diǎn)的值比value大的
            while (p.right.value != null && p.right.value <= value) {
                p = p.right;    //如果沒(méi)有找到就后移直到找到這個(gè)節(jié)點(diǎn)

            }

            //如果找到的這個(gè)節(jié)點(diǎn)不是最底層的話(huà)，就向下移動(dòng)一層，然后循環(huán)再次尋找，總之就是從最高層開(kāi)始，一層一層的尋找
            if (p.down != null) {   //這個(gè)表示上面的循環(huán)沒(méi)有找到的相等的，那么就向下移動(dòng)一層
                p = p.down;
            } else {    //如果到了最底層了，這里的值仍然沒(méi)有找到這個(gè)值，那么就表示不存在這個(gè)值
                if (p.value == value) {   //判斷是否存在value相等的值
//                    System.out.println(p.value + "----->");
                    return p;    //返回節(jié)點(diǎn)
                }

                return null;    //仍然沒(méi)有找到返回null
            }


        }

    }


    /*
    這里是利用上面的查找函數(shù)，找到當(dāng)前需要?jiǎng)h除的節(jié)點(diǎn)，當(dāng)然這個(gè)節(jié)點(diǎn)是最底層的節(jié)點(diǎn)，然后循環(huán)從最底層開(kāi)始刪除所有的節(jié)點(diǎn)
    * */
    public void delete(int value) {
        Node temp = search(value);   //這里返回的必須是最底層的節(jié)點(diǎn)，因?yàn)橐獜淖钕旅娴耐厦嫒縿h除所有層的節(jié)點(diǎn)，否則的話(huà)可能在某一層上仍然存在這個(gè)節(jié)點(diǎn)
        while (temp != null) {
            temp.left.right = temp.right;
            temp.right.left = temp.left;
            temp = temp.up;   //節(jié)點(diǎn)上移，繼續(xù)刪除上一層的節(jié)點(diǎn)
        }

    }

    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("沒(méi)有找到");

        skipList.delete(33);
        skipList.display();


    }
}

跳躍鏈表

雙鏈表

單鏈表

java實(shí)現(xiàn)跳躍鏈表