For the concept of skip lists, and the process of adding, deleting, modifying, and checking skip lists, see this article. Skip List (Skip List) Skip List (Skip List) Skip List (Skip List) Skip List
/** * an implementation of the hop table. * The hop table stores positive integers and does not store duplicates. * /
public class SkipList {
private static final float SKIPLIST_P = 0.5 f;
private static final int MAX_LEVEL = 16;
private int levelCount = 1;
private Node head = new Node(); // start the list
/ * * * /
public Node find(int value) {
Node p = head;
// Start at the top, loop through the bottom pointer
for (int i = levelCount - 1; i >= 0; --i) {
// The inner layer loops through the pointer to the right to find the last position of each layer less than value
while(p.forwards[i] ! =null&& p.forwards[i].data < value) { p = p.forwards[i]; }}// Determine if the value of the original list pair is equal to value, and if so, return the Node
if (p.forwards[0] != null && p.forwards[0].data == value) {
return p.forwards[0];
} else {
return null; }}/** The index is maintained when it is inserted, and the corresponding index is inserted each time it passes through the corresponding level until it reaches the original list */
public void insert(int value) {
// Get the index level
int level = randomLevel();
Node newNode = new Node();
newNode.data = value;
newNode.maxLevel = level;
Node update[] = new Node[level];
for (int i = 0; i < level; ++i) {
update[i] = head;
}
Update [I] at each level, a < value <= b
Node p = head;
// Loop over the downward pointer
for (int i = level - 1; i >= 0; --i) {
// The inner layer loops through the pointer to the right to find the last position of each layer less than value
while(p.forwards[i] ! =null && p.forwards[i].data < value) {
p = p.forwards[i];
}
update[i] = p;// Update [I] is where newNode should be inserted at level I
}
// Start inserting newNode at the corresponding position of each layer. The original pointer is a -> b
for (int i = 0; i < level; ++i) {
// Change the point to newNode.next -> a.ext
newNode.forwards[i] = update[i].forwards[i];
// Change the point to a.ext -> newNode
update[i].forwards[i] = newNode;
}
// After the change, the list point of each layer is changed to a -> newNode -> b
// Update the maximum height
if (levelCount < level) levelCount = level;
}
/ * * delete * /
public void delete(int value) {
Node[] update = new Node[levelCount];
Node p = head;
// As with add, find the corresponding position of the index to be dropped at each level
for (int i = levelCount - 1; i >= 0; --i) {
// The inner loop exits if the value of the next node of p is greater than or equal to value, i.e. the last position of each layer is less than value
while(p.forwards[i] ! =null && p.forwards[i].data < value) {
p = p.forwards[i];
}
// assign p to update[I]
update[i] = p;
}
// The if condition ensures that the value to be deleted exists in the lowest level of the original list
if (p.forwards[0] != null && p.forwards[0].data == value) {
// Delete from the top to the original list
for (int i = levelCount - 1; i >= 0; --i) {
// If the next node of update[I] is equal to value, that is, b == value, then delete that node
if(update[i].forwards[i] ! =null && update[i].forwards[i].data == value) {
// make a.ext point to the next node where the node to be deleted is no longer in the listupdate[i].forwards[i] = update[i].forwards[i].forwards[i]; }}}// Change the height of the hop table, because some index nodes are removed, it may become smaller
while (levelCount > 1 && head.forwards[levelCount] == null){ levelCount--; }}// In theory, the number of elements in the primary index should be 50% of the original data, the number of elements in the secondary index should be 25%, and the number of elements in the tertiary index should be 12.5%, all the way to the top level.
// Because each level here has a 50% chance of promotion. For each newly inserted node, you need to call randomLevel to generate a reasonable number of layers.
// The randomLevel method will randomly generate numbers between 1 and MAX_LEVEL, and:
// returns 1 50% of the time
// a 25% chance of returning 2
// 12.5% chance of returning 3...
private int randomLevel(a) {
int level = 1;
// math.random () will generate a Double between 0 and 1. The higher the SKIPLIST_P, the higher the chance of advancement.
while (Math.random() < SKIPLIST_P && level < MAX_LEVEL)
level += 1;
return level;
}
public void printAll(a) {
Node p = head;
while (p.forwards[0] != null) {
System.out.print(p.forwards[0] + "");
p = p.forwards[0];
}
System.out.println();
}
public class Node {
private int data = -1;
// An array of Node levels containing the i-level Pointers to the previous Node
// Change the value of array index I to logically replace Pointers down or up between levels
private Node forwards[] = new Node[MAX_LEVEL];
private int maxLevel = 0;
@Override
public String toString(a) {
StringBuilder builder = new StringBuilder();
builder.append("{ data: ");
builder.append(data);
builder.append("; levels: ");
builder.append(maxLevel);
builder.append("}");
returnbuilder.toString(); }}}Copy the codeSkipList SkipList: The Beauty of Data Structures and Algorithms