Java實現跳躍表的示例詳解

Posted on by

跳表全稱叫做跳躍表，簡稱跳表，是一個隨機化的數據結構，實質就是一種可以進行二分查找的有序鏈表。跳表在原有的有序列表上面增加多級索引，通過索引來實現快速查找。跳表不僅能提高搜索性能，同時也提高插入和刪除的性能，redis中的有序集合set就是用跳表實現的，面試時候也經常會問。 

這裡我們原始數據個數n=10，以間隔k=2建立索引，則第一層索引10/2=5個，第二層⌈10/2^2⌉=3個，第三層⌈10/2^3⌉=2個，第四層⌈10/2^4⌉=1個。根據上圖我們來分析一下，跳表的結構是一棵樹（除原始數據層外），樹的左指針指向對應的下一層鏈表的節點，右指針指向當前鏈表的下一個節點，且樹高為log(n)，對於每一層需要比較的次數最多為k，則時間復雜度為O(k*log(n))，k為常數項，所以跳表查詢時間復雜度為O(log(n))。因為需要額外的空間存儲索引，是典型的以空間換時間，空間復雜度為O(n)。

接下來我們自己實現一個跳表：

節點數據結構定義：根據跳表結構，節點首先需要一個value存儲當前節點值，需要一個next指針指向同一層的下一個節點，需要一個nodeValue指針指向下一層對應節點，但是這裡為瞭插入刪除方便，引入瞭一個prev指針，指向同一層的上一個節點。

class Node {
    //當前節點值
    private Integer value;
    //當前節點所屬鏈表下一個節點
    private Node next;
    //當前節點所屬鏈表上一個節點
    private Node prev;
    //當前節點指向的另一個索引鏈表/原始值鏈表節點
    private Node nodeValue;
    Node(Integer value) {
        this.value = value;
    }
}

初始化一個跳表：跳表的建立需要在數據有序的基礎上，然後從下往上在下一層的基礎上，間隔k生成當前層的節點，新生成的節點需要與當前層上一個節點連接起來，並且指向生成它的下一層節點。

/**
 * 原始數據鏈表
 */
private Node head ;
/**
 * 最終的跳表結構：保存索引鏈表及原始鏈表
 */
private List<Node> indexList;
/**
 * 跳表層數
 */
private int level;

/**
* 初始化
*/
public void init() {
    //帶頭節點的鏈表，便於操作
    head = new Node(-1);
    head.next = head;
    indexList = new ArrayList<>();
    level = 0;
}
/**
 * 初始化跳表
 * @param k 間隔
 * @param nums 原始數據（已排序）
 */
public void init(int k, int[] nums) {
    //初始化數據鏈表
    Node temp = head;
    for (int num : nums) {
        Node cur = new Node(num);
        cur.prev = temp;
        temp.next = cur;
        temp = temp.next;
    }
    //新節點保存（最底層）
    indexList.add(head);

    //循環生成索引結構，結束條件，當層僅一個元素
    temp = head.next;
    while (true) {
        //當前鏈表第幾個元素
        int i = 0;
        //生成另一條鏈表長度
        int size = 0;
        Node indexNode = new Node(-1);
        indexNode.next = indexNode;
        Node indexNodeTemp = indexNode;
        while (null != temp) {
            //間隔k生成節點
            if (i % k == 0) {
                Node curNode = new Node(temp.value);
                curNode.nodeValue = temp;
                curNode.prev = indexNodeTemp;
                indexNodeTemp.next = curNode;
                indexNodeTemp = indexNodeTemp.next;
                ++ size;
            }
            ++ i;
            temp = temp.next;
        }
        indexList.add(indexNode);
        temp = indexNode.next;
        //當生成的索引鏈表僅1時不需要再繼續生成
        if (size == 1) {
            break;
        }
    }
    level = indexList.size();
}

從跳表中查找元素：從最頂層索引鏈表開始查找，找到第一個大於當前節點的元素，則需要查找的元素在當前節點與之前節點之間，則從當前節點的上一個節點prev往下nodevalue繼續進行查找，直到當前節點值與查找值相等，則直接返回當前節點，返回的節點可能是索引節點，也可能是原始數據節點，如果需要找到原始數據節點，則通過nodeValue繼續往下找。

/**
 * 是否存在num
 * @param num
 * @return
 */
public boolean hasNum(int num) {
    Node result = this.findNum(num);
    return null != result;
}
/**
 * 查找num（返回的可能是索引，也可能是原始數據，根據nodeValue可以判斷，也可以找到原始數據）
 * @param num
 */
public Node findNum(int num) {
    //跳表結構indexList是數據-》第一層索引-》第二層索引-》。。。。
    //1.直接匹配到
    //2.找到第一個大於當前元素的數，找前一個
    Node node = indexList.get(indexList.size() - 1).next;
    Node last = null;
    while (null != node) {
        if (node.value == num) {
            //已經找到元素
            return node;
        }
        if (node.value > num) {
            if (null == last) {
                //比最小值還小
                return null;
            }
            //找到瞭第一個大於num的索引node
            //到下一層去繼續找
            node = last.nodeValue;
            last = null;
            continue;
        }
        last = node;
        node = null != node.next ? node.next : node.nodeValue;
    }
    return null;
}

刪除節點：首先通過上面的查找方法找到目標節點，如果目標節點是索引值，則需要從當前索引層，層層往下刪除包括原始數據鏈表，如果是原始數據值，則直接刪除，暫不調整。

/**
 * 構建索引時：自底向上逐層構建，如果索引需要刪除（當兩個索引之間沒有任何數據時候，刪除）
 * @param num
 * @return
 */
public boolean remove(int num) {
    Node node = this.findNum(num);
    if (null == node) {
        //不需要移除
        return false;
    }
    if (null == node.nodeValue) {
        //數據鏈表，可以直接移除
        //是否最後一個節點
        if (null == node.next) {
            node.prev.next = null;
            return true;
        }
        node.next.prev = node.prev;
        node.prev.next = node.next;
        return true;
    }
    //當前在索引上，自上而下刪除索引及數據
    while (null != node) {
        Node cur = node.nodeValue;
        if (null == node.next) {
            node.prev.next = null;
        } else {
            node.next.prev = node.prev;
            node.prev.next = node.next;
        }
        node = cur;
    }
    return true;
}

新增節點：新增節點時候，如果不對索引進行調整，極端情況下，每次新增的節點都在之前第一層兩個節點之間，當這之間的鏈表越變越長，時間復雜度直接退化為O(n)，所以需要同時新增索引，維持跳表的高效性。但是我們如何新增，有一個方法就是，在新增節點時，隨機選擇k，即第k級索引，從1～k新增索引。

/**
 * 首先需要查找插入位置，如果比最小的還小，直接在前面插入
 * 否則需要從最頂級一直查找到數據鏈表，找到插入位置，插入，在查找的過程中，就可以開始插入索引節點，
 * 從上往下進行插入
 * @param num
 */
public void add(int num) {
    int k = this.generatorLevelK();
    //尋找插入點的過程和查找過程基本一致
    //頂級索引鏈表
    Node node = indexList.get(indexList.size() - 1).next;
    int index = 1;
    while (null != node) {
        //找到第一個node.value >= num的元素，在前面插入
        if (node.value >= num) {
            //已經找到,前插
            if (index >= k) {
                Node newNode = new Node(num);
                Node temp = node.prev;
                newNode.next = temp.next;
                temp.next.prev = newNode;
                newNode.prev = temp;
                temp.next = newNode;
            }
            //找的時候往後面找的，但是當前已經先於num瞭，下一次再往後面找，就出現問題
            if (null == node.prev.prev) {
                //第一個節點就符合條件
                node = node.nodeValue;
                continue;
            }
            node = node.prev.nodeValue;
            ++ index;
            continue;
        }

        //沒有找到，但是當前已經是鏈表最後一個元素瞭
        if (null == node.next) {
            if (index >= k) {
                Node newNode = new Node(num);
                newNode.prev = node;
                node.next = newNode;
            }
            if (null == node.prev.prev) {
                //第一個節點就符合條件
                node = node.nodeValue;
                continue;
            }
            node = node.prev.nodeValue;
            ++ index;
            continue;
        }

        node = node.next;
    }

}

private int generatorLevelK() {
    Random random = new Random();
    return random.nextInt(level);
}

至此，我們實現瞭一個跳表的定義，初始化，查找，節點新增與刪除。

到此這篇關於Java實現跳躍表的示例詳解的文章就介紹到這瞭,更多相關Java跳躍表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：