1. python
class Node:
value = None
levels = []
class Skiplist:
def __init__(self):
self.head = Node()
self.max_level = 500
self.head.levels = [None for i in range(self.max_level)]
self.currLevel = 1
def search(self, target: int) -> bool:
cu = self.head
for i in range(self.currLevel-1, -1, -1):
while cu.levels[i] and cu.levels[i].value < target:
cu = cu.levels[i]
if cu.levels[i] and cu.levels[i].value == target:
return True
return False
def add(self, num: int) -> None:
new_level = self.get_level()
levels = [None for i in range(new_level)]
insert_node = Node()
insert_node.value = num
insert_node.levels = levels
cu = self.head
for i in range(self.currLevel-1, -1, -1):
while cu.levels[i] is not None and cu.levels[i].value < num:
cu = cu.levels[i]
if i > new_level - 1:
continue
if cu.levels[i] is None:
cu.levels[i] = insert_node
else:
tmp = cu.levels[i]
insert_node.levels[i] = tmp
cu.levels[i] = insert_node
if new_level > self.currLevel:
for i in range(self.currLevel, new_level):
self.head.levels[i] = insert_node
self.currLevel = new_level
def erase(self, num: int) -> bool:
flag = False
cu = self.head
for i in range(self.currLevel-1, -1, -1):
while cu.levels[i] and cu.levels[i].value < num:
cu = cu.levels[i]
if cu.levels[i] and cu.levels[i].value == num:
flag = True
cu.levels[i] = cu.levels[i].levels[i]
return flag
def get_level(self):
level = 1
while random.random() < 0.25 and level < self.max_level:
level = level + 1
return level
2. java
public class Skiplist {
static class Node {
private Integer value;
private Node[] nexts;
public static Node init(Integer val, int level) {
Node node = new Node();
node.value = val;
node.nexts = new Node[level];
return node;
}
}
private static final int MAX_LEVEL = 32;
private final Node head;
private int currLevel;
public Skiplist() {
this.head = Node.init(null, MAX_LEVEL);
this.currLevel = 1;
}
public boolean search(int target) {
Node cursor = this.head;
for (int i = this.currLevel - 1; i >= 0; i--) {
cursor = findClosest(cursor, i, target);
if (cursor.nexts[i] != null && cursor.nexts[i].value == target) {
return true;
}
}
return false;
}
public void add(int num) {
Node cursor = this.head;
int newLevel = randomLevel();
Node insert = Node.init(num, newLevel);
for (int i = this.currLevel - 1; i >= 0; i--) {
cursor = findClosest(cursor, i, num);
if (i > (newLevel-1)) {
continue;
}
if (cursor.nexts[i] == null) {
cursor.nexts[i] = insert;
} else {
Node tmp = cursor.nexts[i];
cursor.nexts[i] = insert;
insert.nexts[i] = tmp;
}
}
if (newLevel > currLevel) {
for (int i = currLevel; i < newLevel; i++) {
head.nexts[i] = insert;
}
currLevel = newLevel;
}
}
public boolean erase(int num) {
Node cursor = this.head;
boolean erased = false;
for (int i = this.currLevel - 1; i>=0; i--) {
cursor = findClosest(cursor, i, num);
if (cursor.nexts[i] != null && cursor.nexts[i].value == num) {
cursor.nexts[i] = cursor.nexts[i].nexts[i];
erased = true;
}
}
return erased;
}
private int randomLevel() {
int level = 1;
while (Math.random() < 0.25 && level < MAX_LEVEL) {
level += 1;
}
return level;
}
private Node findClosest(Node start, int levelIdx, int target) {
while (start.nexts[levelIdx] != null && start.nexts[levelIdx].value < target) {
start = start.nexts[levelIdx];
}
return start;
}
public static void main(String[] args) {
Skiplist skiplist = new Skiplist();
skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
System.out.println(skiplist.search(0));
System.out.println(skiplist.erase(0));
System.out.println(skiplist.search(1));
System.out.println(skiplist.erase(1));
System.out.println(skiplist.search(1));
}
}
|
