原文链接及讲解:
详解Java中跳跃表的原理和实现
java跳表实现
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;
/**
* java跳表实现
*
* @author lyn
* @date 2023/6/30 18:50
*/
public class OwnSkipList {
private static final int MAX_LEVEL = 16;
private static final float P = 0.5f;
private static final int MAX_INT = 0x7fffffff;
class Node {
int val;
Node[] forwards = new Node[MAX_LEVEL];
}
private Node head;
private int curLevel;
private Node[] upData;
public OwnSkipList() {
init();
}
/**
* 初始化
*/
private void init() {
curLevel = 0;
head = getNewNode(-MAX_INT);
upData = new Node[MAX_LEVEL];
for (int i = 0; i < MAX_LEVEL; i++) {
upData[i] = new Node();
}
}
private Node getNewNode(int value) {
Node node = new Node();
for (int i = 0; i < MAX_LEVEL; i++) {
node.forwards[i] = null;
}
node.val = value;
return node;
}
/**
* 插入元素
*
* @param value 值
*/
public void insert(int value) {
int lev = randomLevel();
if (lev > curLevel) {
curLevel = lev;
}
//寻找每层最接近的元素
find(value);
//创建一个新节点
Node newNode = getNewNode(value);
//插入操作
for (int i = 0; i <= lev; i++) {
newNode.forwards[i] = upData[i].forwards[i];
upData[i].forwards[i] = newNode;
}
}
public void delete(int value) {
Node zeroLevelNode = find(value);
//如果零层都没有,则结束
if (zeroLevelNode.forwards[0] == null || zeroLevelNode.forwards[0].val != value) {
return;
}
System.out.println("删除元素 " + value + "\n");
// 删除操作
for (int i = curLevel; i >= 0; i--) {
if (upData[i].forwards[i] != null && upData[i].forwards[i].val == value) {
upData[i].forwards[i] = upData[i].forwards[i].forwards[i];
}
}
//删除空链
while (curLevel > 0 && head.forwards[curLevel] == null) {
curLevel--;
}
}
/**
* 查找最接近val的元素
*
* @param value 值
*/
private Node find(int value) {
Node tem = head;
for (int i = curLevel; i >= 0; i--) {
while (tem.forwards[i] != null && tem.forwards[i].val < value) {
tem = tem.forwards[i];
}
//记录搜索过程中各级走过的最大节点位置
upData[i] = tem;
}
return tem;
}
/**
* 随机产生插入元素高度
*
* @return 高度
*/
private int randomLevel() {
int lev = 0;
while (Math.random() < P && lev < MAX_LEVEL - 1) {
lev++;
}
return lev;
}
public void print(int i) {
// 遍历
Node p = head.forwards[i];
if (p == null) {
return;
}
while (p != null) {
System.out.printf("%d ", p.val);
p = p.forwards[i];
}
System.out.printf("\n");
}
/**
* 遍历所有层
*/
public void printAll() {
for (int i = curLevel; i >= 0; i--) {
System.out.printf("curLevel %d: ", i);
print(i);
}
System.out.println();
}
public static void main(String[] args) {
OwnSkipList skipList = new OwnSkipList();
List<Integer> list = Stream.iterate(1, s -> s + 1).limit(50).collect(Collectors.toList());
Collections.shuffle(list);
for (Integer element : list) {
skipList.insert(element);
}
skipList.printAll();
skipList.delete(21);
skipList.printAll();
}
}
标签:Node,Java,forwards,int,private,curLevel,详解,value,跳跃
From: https://www.cnblogs.com/lyn8100/p/17515362.html