Java 跳表实现：代码示例与详解

下面是一个简单的 Java 实现跳表的示例代码：

import java.util.Random;

class SkipListNode {
    int value;
    SkipListNode next;
    SkipListNode down;

    public SkipListNode(int value) {
        this.value = value;
        this.next = null;
        this.down = null;
    }
}

public class SkipList {
    private SkipListNode head;
    private Random random;

    public SkipList() {
        head = new SkipListNode(Integer.MIN_VALUE);
        random = new Random();
    }

    public void insert(int value) {
        SkipListNode newNode = new SkipListNode(value);
        SkipListNode cur = head;

        while (cur != null) {
            while (cur.next != null && cur.next.value < value) {
                cur = cur.next;
            }

            if (cur.down != null) {
                cur = cur.down;
            } else {
                break;
            }
        }

        newNode.next = cur.next;
        cur.next = newNode;

        // 可以根据一定的概率决定是否要添加新的层
        while (random.nextDouble() < 0.5) {
            SkipListNode newHead = new SkipListNode(Integer.MIN_VALUE);
            newHead.down = head;
            head = newHead;

            SkipListNode newCur = head;
            while (cur != null) {
                SkipListNode newNext = new SkipListNode(value);
                newNext.next = cur.next;
                cur.next = newNext;

                newCur.down = newNext;
                newCur = newCur.next;

                cur = cur.down;
            }
        }
    }

    public boolean search(int value) {
        SkipListNode cur = head;
        while (cur != null) {
            while (cur.next != null && cur.next.value < value) {
                cur = cur.next;
            }

            if (cur.next != null && cur.next.value == value) {
                return true;
            }

            cur = cur.down;
        }
        return false;
    }

    public boolean delete(int value) {
        SkipListNode cur = head;
        boolean found = false;

        while (cur != null) {
            while (cur.next != null && cur.next.value < value) {
                cur = cur.next;
            }

            if (cur.next != null && cur.next.value == value) {
                cur.next = cur.next.next;
                found = true;
            }

            cur = cur.down;
        }

        return found;
    }

    public void printList() {
        SkipListNode cur = head;
        while (cur != null) {
            SkipListNode node = cur;
            while (node != null) {
                System.out.print(node.value + " ");
                node = node.next;
            }
            System.out.println();
            cur = cur.down;
        }
    }

    public static void main(String[] args) {
        SkipList skipList = new SkipList();
        skipList.insert(1);
        skipList.insert(4);
        skipList.insert(2);
        skipList.insert(3);

        skipList.printList();

        System.out.println("Search 2: " + skipList.search(2));
        System.out.println("Search 5: " + skipList.search(5));

        skipList.delete(2);

        skipList.printList();
    }
}

这个示例代码实现了一个简单的跳表类SkipList，其中使用SkipListNode表示跳表的节点。在SkipList类中，实现了插入insert、搜索search和删除delete等操作。在main方法中演示了插入了四个元素并打印跳表的结构，然后进行了搜索和删除操作，并打印修改后的跳表结构。

跳表数据结构

跳表是一种概率性数据结构，它在链表的基础上增加了多级索引，以提高搜索效率。跳表通过在不同层级的节点之间建立连接，形成多层链表，从而快速定位目标节点。

实现细节

SkipListNode 类： 表示跳表的节点，包含值value、下一节点指针next和下一层节点指针down。
SkipList 类： 表示跳表，包含头节点head和随机数生成器random。
insert 方法： 插入新节点时，首先按照值大小找到插入位置，然后在所有层级都插入该节点。同时，根据随机概率决定是否新建一层，并将新层与其他层连接起来。
search 方法： 搜索目标节点时，从顶层开始，沿着next指针遍历，如果当前节点的值小于目标值，则继续遍历；如果当前节点的值等于目标值，则返回true；如果当前节点的值大于目标值，则向下移动到下一层。
delete 方法： 删除目标节点时，从顶层开始，按照值大小找到目标节点，并将其从所有层级中删除。

优点

平均搜索时间复杂度为 O(log n)，接近于二叉树。
实现简单，代码易于理解。

缺点

由于跳表是概率性数据结构，最坏情况下搜索时间复杂度为 O(n)。
占用更多内存空间，因为它需要保存多层索引。

应用场景

数据库索引
分布式缓存
数据流处理

希望本文能帮助你理解跳表的基本原理和实现方法。如果你有任何问题，请随时提出。