是什么让普通的链表也能达到二分查找的效率，你知道吗？
@ClassName SkipList
@Description 跳表
*/
public class SkipList {
private static final int MAX_LEVEL = 16;
private int levelCount = 1;
/**
带头链表
*/
private Node head = new Node(MAX_LEVEL);
private Random r = new Random();
public Node find(int value) {
Node p = head;
// 从最大层开始查找，找到前一节点，通过--i，移动到下层再开始查找
for (int i = levelCount - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
// 找到前一节点
p = p.forwards[i];
}
}
if (p.forwards[0] != null && p.forwards[0].data == value) {
return p.forwards[0];
} else {
return null;
}
}
/**
优化了作者 zheng 的插入方法
@param value 值
*/
public void insert(int value) {
int level = head.forwards[0] == null ? 1 : randomLevel();
// 每次只增加一层，如果条件满足
if (level > levelCount) {
level = ++levelCount;
}
Node newNode = new Node(level);
newNode.data = value;
Node update[] = new Node[level];
for (int i = 0; i < level; ++i) {
update[i] = head;
}
Node p = head;
// 从最大层开始查找，找到前一节点，通过--i，移动到下层再开始查找
for (int i = levelCount - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
// 找到前一节点
p = p.forwards[i];
}
// levelCount 会 > level，所以加上判断
if (level > i) {
update[i] = p;
}
}
for (int i = 0; i < level; ++i) {
newNode.forwards[i] = update[i].forwards[i];
update[i].forwards[i] = newNode;
}
}
/**
优化了作者 zheng 的插入方法 2
@param value 值
*/
public void insert2(int value) {
int level = head.forwards[0] == null ? 1 : randomLevel();
// 每次只增加一层，如果条件满足
if (level > levelCount) {
level = ++levelCount;
}
Node newNode = new Node(level);
newNode.data = value;
Node p = head;
// 从最大层开始查找，找到前一节点，通过--i，移动到下层再开始查找
for (int i = levelCount - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
// 找到前一节点
p = p.forwards[i];
}
// levelCount 会 > level，所以加上判断
if (level > i) {
if (p.forwards[i] == null) {
p.forwards[i] = newNode;
} else {
Node next = p.forwards[i];
p.forwards[i] = newNode;
newNode.forwards[i] = next;
}
}
}
}
/**
作者 zheng 的插入方法，未优化前，优化后参见上面 insert()
@param value
@param level 0 表示随机层数，不为 0，表示指定层数，指定层数
*/
public void insert(int value, int level) {
// 随机一个层数
if (level == 0) {
level = randomLevel();
}
// 创建新节点
Node newNode = new Node(level);
newNode.data = value;
// 表示从最大层到低层，都要有节点数据
newNode.maxLevel = level;
// 记录要更新的层数，表示新节点要更新到哪几层
Node update[] = new Node[level];
for (int i = 0; i < level; ++i) {
update[i] = head;
}
/**
1，说明：层是从下到上的，这里最下层编号是 0，最上层编号是 15
2，这里没有从已有数据最大层（编号最大）开始找，（而是随机层的最大层）导致有些问题。
如果数据量为 1 亿，随机 level=1 ，那么插入时间复杂度为 O（n）
*/
Node p = head;
for (int i = level - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
// 这里 update[i]表示当前层节点的前一节点，因为要找到前一节点，才好插入数据
update[i] = p;
}
// 将每一层节点和后面节点关联
for (int i = 0; i < level; ++i) {
// 记录当前层节点后面节点指针
newNode.forwards[i] = update[i].forwards[i];
// 前一个节点的指针，指向当前节点
update[i].forwards[i] = newNode;
}
// 更新层高
if (levelCount < level){
levelCount = level;
}
}
public void delete(int value) {
Node[] update = new Node[levelCount];
Node p = head;
for (int i = levelCount - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
update[i] = p;
}
if (p.forwards[0] != null && p.forwards[0].data == value) {
for (int i = levelCount - 1; i >= 0; --i) {
if (update[i].forwards[i] != null && update[i].forwards[i].data == value) {
update[i].forwards[i] = update[i].forwards[i].forwards[i];
}
}
}
}
/**
随机 level 次，如果是奇数层数 +1，防止伪随机
@return
*/
private int randomLevel() {
int level = 1;
for (int i = 1; i < MAX_LEVEL; ++i) {
if (r.nextInt() % 2 == 1) {
level++;
}
}
return level;
}
/**
打印每个节点数据和最大层数
*/
public void printAll() {
Node p = head;
while (p.forwards[0] != null) {
System.out.print(p.forwards[0] + " ");
p = p.forwards[0];
}
System.out.println();
}
/**
打印所有数据
*/
public void printAll_beautiful() {
Node p = head;
Node[] c = p.forwards;
Node[] d = c;
int maxLevel = c.length;
for (int i = maxLevel - 1; i >= 0; i--) {
do {
System.out.print((d[i] != null ? d[i].data : null) + ":" + i + "-------");
} while (d[i] != null && (d = d[i].forwards)[i] != null);
System.out.println();
d = c;
}
}
/**
跳表的节点，每个节点记录了当前节点数据和所在层数数据
*/
public class Node {
private int data = -1;
/**
表示当前节点位置的下一个节点所有层的数据，从上层切换到下层，就是数组下标-1，
forwards[3]表示当前节点在第三层的下一个节点。
*/
private Node forwards[];
/**
这个值其实可以不用，看优化 insert()
*/
private int maxLevel = 0;
public Node(int level) {
forwards = new Node[level];
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("{ data: ");
builder.append(data);
builder.append("; levels: ");
builder.append(maxLevel);
builder.append(" }");
return builder.toString();
}
}
public static void main(String[] args) {
SkipList list = new SkipList();
list.insert(1, 3);
list.insert(2, 3);
list.insert(3, 2);
list.insert(4, 4);
list.insert(5, 10);
list.insert(6, 4);
list.insert(8, 5);
list.insert(7, 4);
list.printAll_beautiful();
list.printAll();
SkipList list2 = new SkipList();
list2.insert2(1);
list2.insert2(2);
list2.insert2(6);
list2.insert2(7);
list2.insert2(8);
list2.insert2(3);
list2.insert2(4);
list2.insert2(5);
System.out.println();
list2.printAll_beautiful();
}
}
打印结果
`null:15-------
null:14-------
null:13-------
null:12-------
null:11-------
null:10-------
5:9-------
5:8-------
5:7-------
5:6-------
5:5-------
5:4-------8:4-------
4:3-------5:3-------6:3-------7:3-------8:3-------
1:2-------2:2-------4:2-------5:2-------6:2-------7:2-------8:2-------
1:1-------2:1-------3:1-------4:1-------5:1-------6:1-------7:1-------8:1-------
1:0-------2:0-------3:0-------4:0-------5:0-------6:0-------7:0-------8:0-------
{ data: 1; levels: 3 } { data: 2; levels: 3 } { data: 3; levels: 2 } { data: 4; levels: 4 } { data: 5; levels: 10 } { data: 6; levels: 4 } { data: 7; levels: 4 } { data: 8; levels: 5 }
null:15-------
还未添加个人签名 2021.03.18 加入
还未添加个人简介
评论