跳表是一种随机化的数据结构,基于链表实现,通过维护多层链表实现对有序链表的快速访问,平均查找、插入和删除时间复杂度均为O(log n)。跳表是对有序链表的一种优化,在链表的基础上,增加了多级索引,以空间换时间,使得操作效率接近二叉查找树。
跳表是一种基于有序链表的数据结构,通过添加额外的"跳跃"链接,实现了对链表的快速查找。传统的有序链表查找需要从头开始一个一个节点遍历,时间复杂度为O(n),而跳表通过构建多层索引,可以达到平均O(log n)的搜索效率,接近于二叉搜索树。
跳表的核心构想可以类比为图书馆的索引系统或多层电梯:
在跳表中,每个节点包含以下几个组成部分:
查找过程从最高层开始,沿着当前层前进,直到遇到大于或等于目标值的节点:
插入新节点的步骤:
删除节点的步骤:
▼Java复制代码import java.util.Random; public class SkipList<T extends Comparable<T>> { private static final int MAX_LEVEL = 16; // 最大层数 private static final double P = 0.5; // 提升层级的概率 private int level; // 当前跳表的最大层数 private final Node<T> header; // 头节点 private final Random random; // 用于随机层数的生成 // 节点定义 private static class Node<T extends Comparable<T>> { T value; // 节点值 Node<T>[] forward; // 前进指针数组 @SuppressWarnings("unchecked") Node(T value, int level) { this.value = value; this.forward = new Node[level + 1]; } } // 构造函数 public SkipList() { this.level = 0; this.header = new Node<>(null, MAX_LEVEL); this.random = new Random(); } // 随机生成层数 private int randomLevel() { int lvl = 0; while (lvl < MAX_LEVEL && random.nextDouble() < P) { lvl++; } return lvl; } // 查找操作 public Node<T> search(T value) { Node<T> current = header; // 从最高层开始查找 for (int i = level; i >= 0; i--) { // 在当前层向前移动,直到找到大于等于目标值的节点 while (current.forward[i] != null && current.forward[i].value.compareTo(value) < 0) { current = current.forward[i]; } } // 现在我们在第0层,并且current是目标值的前一个节点 current = current.forward[0]; // 检查是否找到目标值 if (current != null && current.value.compareTo(value) == 0) { return current; } else { return null; } } // 插入操作 public void insert(T value) { @SuppressWarnings("unchecked") Node<T>[] update = new Node[MAX_LEVEL + 1]; Node<T> current = header; // 查找插入位置并记录每层的前驱节点 for (int i = level; i >= 0; i--) { while (current.forward[i] != null && current.forward[i].value.compareTo(value) < 0) { current = current.forward[i]; } update[i] = current; } // 获取新节点的随机层数 int newLevel = randomLevel(); // 如果新层数比当前跳表的最大层数大,更新跳表层数 if (newLevel > level) { for (int i = level + 1; i <= newLevel; i++) { update[i] = header; } level = newLevel; } // 创建新节点 Node<T> newNode = new Node<>(value, newLevel); // 插入节点到各层链表中 for (int i = 0; i <= newLevel; i++) { newNode.forward[i] = update[i].forward[i]; update[i].forward[i] = newNode; } } // 删除操作 public void delete(T value) { @SuppressWarnings("unchecked") Node<T>[] update = new Node[MAX_LEVEL + 1]; Node<T> current = header; // 查找删除位置并记录每层的前驱节点 for (int i = level; i >= 0; i--) { while (current.forward[i] != null && current.forward[i].value.compareTo(value) < 0) { current = current.forward[i]; } update[i] = current; } current = current.forward[0]; // 如果找到节点,进行删除 if (current != null && current.value.compareTo(value) == 0) { for (int i = 0; i <= level; i++) { // 如果当前层的前驱节点指向要删除的节点,则修改指针 if (update[i].forward[i] == current) { update[i].forward[i] = current.forward[i]; } } // 更新跳表的最大层数 while (level > 0 && header.forward[level] == null) { level--; } } } // 打印跳表内容(用于调试) public void printSkipList() { System.out.println("Skip List Structure:"); for (int i = level; i >= 0; i--) { System.out.print("Level " + i + ": "); Node<T> node = header.forward[i]; while (node != null) { System.out.print(node.value + " "); node = node.forward[i]; } System.out.println(); } } }