跳表（SkipList）是一种基于有序链表的扩展结构，通过维护多层级的前向指针来提升查找、插入、删除操作的效率，时间复杂度可以稳定在O(log n)。泛型节点链表是跳表的基础，它需要在支持任意可比较类型的同时，维护多层级的指针关系，实现时需要兼顾类型安全和结构合理性。
跳表泛型节点的设计思路
跳表的每个节点需要存储三个核心部分：节点的数据值、节点所在的层级对应的前向指针数组、节点的层级高度。由于跳表需要支持任意数据类型，因此节点类需要定义为泛型类，同时要求泛型类型实现Comparable接口，保证节点之间可以进行大小比较。
前向指针数组的长度等于节点所在的层级高度，每一层的指针指向同层级的下一个节点。节点的层级高度通常在节点创建时随机生成，避免结构退化。
泛型节点类的基础定义
首先定义泛型节点类SkipListNode，泛型参数T需要约束为Comparable<T>的子类：
import java.util.ArrayList;
import java.util.List;
/**
* 跳表泛型节点类
* @param <T> 节点存储的数据类型，需要实现Comparable接口
*/
public class SkipListNode<T extends Comparable<T>> {
// 节点存储的数据
private T data;
// 节点的前向指针数组，每个元素指向同层级的下一个节点
private List<SkipListNode<T>> forward;
// 节点的最高层级（从0开始计数）
private int level;
/**
* 构造节点
* @param data 节点数据
* @param level 节点的层级高度
*/
public SkipListNode(T data, int level) {
this.data = data;
this.level = level;
// 初始化前向指针数组，长度为level+1，因为层级从0开始
this.forward = new ArrayList<>(level + 1);
for (int i = 0; i <= level; i++) {
forward.add(null);
}
}
// getter和setter方法
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public List<SkipListNode<T>> getForward() {
return forward;
}
public void setForward(List<SkipListNode<T>> forward) {
this.forward = forward;
}
public int getLevel() {
return level;
}
public void setLevel(int level) {
this.level = level;
// 如果新的层级比原来的高，需要扩容前向指针数组
if (forward.size() < level + 1) {
for (int i = forward.size(); i <= level; i++) {
forward.add(null);
}
}
}
/**
* 获取指定层级的下一个节点
* @param layer 层级索引
* @return 下一个节点，不存在则返回null
*/
public SkipListNode<T> getNext(int layer) {
if (layer < 0 || layer > level) {
return null;
}
return forward.get(layer);
}
/**
* 设置指定层级的下一个节点
* @param layer 层级索引
* @param node 下一个节点
*/
public void setNext(int layer, SkipListNode<T> node) {
if (layer >= 0 && layer <= level) {
forward.set(layer, node);
}
}
}
跳表泛型链表的核心操作实现
跳表的链表结构需要维护一个头节点，头节点的层级通常是跳表的最大层级，头节点不存储实际数据，仅作为每层链表的起始点。下面实现跳表链表的基础操作，包括节点查找、插入、删除。
跳表链表类的定义
定义SkipList类，包含头节点、当前最大层级、随机层级生成方法等核心成员：
import java.util.Random;
public class SkipList<T extends Comparable<T>> {
// 跳表的最大允许层级
private static final int MAX_LEVEL = 16;
// 头节点，不存储实际数据
private SkipListNode<T> head;
// 当前跳表的实际最大层级
private int currentLevel;
// 随机数生成器，用于生成节点层级
private Random random;
// 节点层级生成的概率，通常取0.5
private static final double PROBABILITY = 0.5;
public SkipList() {
// 头节点的层级初始化为MAX_LEVEL-1
this.head = new SkipListNode<>(null, MAX_LEVEL - 1);
this.currentLevel = 0;
this.random = new Random();
}
/**
* 随机生成节点的层级
* @return 节点层级，范围0到MAX_LEVEL-1
*/
private int randomLevel() {
int level = 0;
while (random.nextDouble() < PROBABILITY && level < MAX_LEVEL - 1) {
level++;
}
return level;
}
}
查找节点的实现
跳表的查找从最高层级开始，每层找到小于目标值的最右节点，然后下降到下一层继续查找，直到第0层：
/**
* 查找跳表中是否存在目标数据
* @param target 目标数据
* @return 存在则返回对应节点，不存在返回null
*/
public SkipListNode<T> search(T target) {
if (target == null) {
return null;
}
SkipListNode<T> current = head;
// 从最高层级开始向下查找
for (int i = currentLevel; i >= 0; i--) {
// 在当前层级找到小于target的最右节点
while (current.getNext(i) != null && current.getNext(i).getData().compareTo(target) < 0) {
current = current.getNext(i);
}
}
// 此时current是第0层小于target的最右节点，检查下一个节点是否是target
current = current.getNext(0);
if (current != null && current.getData().compareTo(target) == 0) {
return current;
}
return null;
}
插入节点的实现
插入节点需要先找到每层需要更新指针的前驱节点，然后随机生成新节点的层级，更新对应层级的指针关系：
/**
* 向跳表中插入数据
* @param data 待插入的数据
*/
public void insert(T data) {
if (data == null) {
return;
}
// 存储每层需要更新的前驱节点
List<SkipListNode<T>> update = new ArrayList<>(MAX_LEVEL);
for (int i = 0; i < MAX_LEVEL; i++) {
update.add(null);
}
SkipListNode<T> current = head;
// 从最高层级开始找到每层的前驱节点
for (int i = currentLevel; i >= 0; i--) {
while (current.getNext(i) != null && current.getNext(i).getData().compareTo(data) < 0) {
current = current.getNext(i);
}
update.set(i, current);
}
// 到达第0层，检查是否已存在相同数据
current = current.getNext(0);
if (current != null && current.getData().compareTo(data) == 0) {
// 已存在则更新数据（根据需求可选）
current.setData(data);
return;
}
// 生成新节点的层级
int newLevel = randomLevel();
// 如果新节点的层级比当前最大层级高，更新头节点和前驱节点
if (newLevel > currentLevel) {
for (int i = currentLevel + 1; i <= newLevel; i++) {
update.set(i, head);
}
currentLevel = newLevel;
}
// 创建新节点
SkipListNode<T> newNode = new SkipListNode<>(data, newLevel);
// 更新每层的指针
for (int i = 0; i <= newLevel; i++) {
newNode.setNext(i, update.get(i).getNext(i));
update.get(i).setNext(i, newNode);
}
}
删除节点的实现
删除节点同样需要先找到每层需要更新指针的前驱节点，然后将对应层级的指针跳过待删除节点：
/**
* 从跳表中删除数据
* @param data 待删除的数据
* @return 删除成功返回true，不存在返回false
*/
public boolean delete(T data) {
if (data == null) {
return false;
}
// 存储每层需要更新的前驱节点
List<SkipListNode<T>> update = new ArrayList<>(MAX_LEVEL);
for (int i = 0; i < MAX_LEVEL; i++) {
update.add(null);
}
SkipListNode<T> current = head;
// 从最高层级开始找到每层的前驱节点
for (int i = currentLevel; i >= 0; i--) {
while (current.getNext(i) != null && current.getNext(i).getData().compareTo(data) < 0) {
current = current.getNext(i);
}
update.set(i, current);
}
// 到达第0层，检查下一个节点是否是待删除节点
current = current.getNext(0);
if (current == null || current.getData().compareTo(data) != 0) {
// 节点不存在
return false;
}
// 更新每层的指针，跳过待删除节点
for (int i = 0; i <= current.getLevel(); i++) {
if (update.get(i).getNext(i) == current) {
update.get(i).setNext(i, current.getNext(i));
}
}
// 如果删除的是最高层级的节点，需要更新currentLevel
while (currentLevel > 0 && head.getNext(currentLevel) == null) {
currentLevel--;
}
return true;
}
实现时的注意事项
- 泛型约束必须正确，保证
T实现Comparable<T>接口，否则节点之间无法比较大小，跳表无法正常工作。 - 前向指针数组的初始化长度要和节点层级匹配，层级从0开始计数，因此数组长度应为
level + 1。 - 随机层级生成的概率和最大层级需要根据实际数据量调整，通常最大层级取
log2(数据量)左右，概率取0.5可以保证层级分布均匀。 - 插入和删除操作时要同时更新所有相关层级的指针，避免链表断裂。
- 头节点不存储实际数据，仅作为每层链表的起始点，操作时要避免修改头节点的数据值。
测试示例
下面给出简单的测试代码，验证泛型节点链表的实现是否正确：
public class SkipListTest {
public static void main(String[] args) {
SkipList<Integer> skipList = new SkipList<>();
// 插入数据
skipList.insert(3);
skipList.insert(1);
skipList.insert(5);
skipList.insert(2);
skipList.insert(4);
// 查找数据
SkipListNode<Integer> node = skipList.search(3);
System.out.println(node != null ? "找到节点: " + node.getData() : "未找到节点");
// 删除数据
boolean deleted = skipList.delete(1);
System.out.println(deleted ? "删除成功" : "删除失败");
// 再次查找已删除的节点
node = skipList.search(1);
System.out.println(node != null ? "找到节点: " + node.getData() : "未找到节点");
}
}