## Pay attention to the official account and exchange with each other. Search by WeChat: Sneak ahead.

## What is a jump list

The balance data structures often used in development include B number, red black number and AVL number. But if you implement one of them, it is very difficult and takes time to implement. The jump linked list is a fast search data structure based on the linked list array. At present, it is used by the open source software Redis and LevelDB. Its efficiency is comparable to that of red black tree and AVL tree

## Jump linked list structure

### structure

public class SkipList<T> { //Head and tail of jump table private SkipListNode<T> head; //The length of the elements contained in the jump table private int length; //The historical maximum number of layers of the skip table public int maxLevel; public SecureRandom random; private static final int MAX_LEVEL = 31; public SkipList() { //Initialize the head and tail nodes and their relationship head = new SkipListNode<>(SkipListNode.HEAD_SCORE, null, MAX_LEVEL); //Initialization size, layer, random length = 0; maxLevel = 0; // The number of layers is calculated from zero random = new SecureRandom(); } ...

- Header: points to the header node of the jump table
- maxLevel: records the layers of the node with the largest number of layers in the current hop table
- Length: the length of the elements in the linked list

### node

The composition of the jump linked list node: the front node, the back node, the score (the key value of the map), and the storage object value

public class SkipListNode<T> { //Score value sorted in the skip table public double score; public T value; public int level; // Front and rear nodes public SkipListNode<T> next,pre; //Layer formed by upper and lower nodes public SkipListNode<T>[] levelNode; private SkipListNode(double score, int level){ this.score = score; this.level = level; } public SkipListNode(double score, T value, int level) { this.score = score; this.value = value; this.level = level; this.levelNode = new SkipListNode[level+1]; //Initialize SkipListNode and node of each layer for (int i = level; i > 0; --i) { levelNode[i] = new SkipListNode<T>(score, level); levelNode[i].levelNode = levelNode; } this.levelNode[0] = this; } @Override public String toString() { return "Node[score=" + score + ", value=" + value + "]"; } }

### Jump table is to trade space for time

- The jump linked list node I implemented includes a levelNode member attribute. It is the node layer. The key point of fast access to jump linked list is it
- We usually access an array in order, and the efficiency of jump linked list is higher than that of array linked list, because it uses node layer to store multi-level indexes to form a sparse index, so it needs more memory space

### How fast is the jump list

- If a linked list has n nodes and one node is extracted from every two nodes to establish an index, the number of nodes of the first layer index is about n/2, the number of nodes of the second layer index is about n/4, and so on. The number of nodes of the m-layer index is about n/(2^m)
- When accessing data, you can locate the m-1 layer index data from the m-layer index query. m-1 is about 1 / 2 of m layer. That is, the optimal time complexity is O(log/N)
- Worst case scenario. In the actual implementation, each layer of index cannot be halved by the amount of data each time. Therefore, in a compromise way, the index of each layer is randomly built with full data. In other words, the worst-case time complexity is O(N), but the optimal time complexity remains unchanged

## query

- The query starts by traversing the index m of the highest maxLevel. Follow the steps below to find the left node equal to or closest to score
- 1: If the next node score of the same layer index is less than the query score, skip to the next node. cur = next
- 2: If next is empty. Or the score of the next node is greater than the query score. Then skip to the next layer m-1 index and cycle 2
- Cycle steps 1 and 2 until the access node score is consistent with the query score, or the index layer is zero

// SkipList private SkipListNode<T> findNearestNode(double score) { int curLevel = maxLevel; SkipListNode<T> cur = head.levelNode[curLevel]; SkipListNode<T> next = cur.next; // The score is the same as the current node or next is null while (score != cur.score && curLevel > 0) { // 1 right next traversal if (next != null && score >= next.levelNode[0].score) { cur = next; } next = cur.levelNode[curLevel].next; // 2. Traverse down and reduce the number of layers by 1 while ((next == null || score < next.levelNode[0].score) && curLevel > 0) { next = cur.levelNode[--curLevel].next; } } // The bottom node. return cur.levelNode[0]; } public SkipListNode<T> get(double score) { //Returns the node closest to the score at the bottom of the jump table SkipListNode<T> p = findNearestNode(score); //If the score is the same, this node is returned return p.score == score ? p : null; }

## insert

- If the score exists, replace value
- If the node corresponding to the score does not exist, a random index level (value 0 ~ 31) is selected. Then add 0 to the index of the level layer by relying on the node attribute levelNode

//SkipList public T put(double score, T value) { //First, get the node closest to the key at the bottom of the hop table SkipListNode<T> p = findNearestNode(score); if (p.score == score) { // In the jump table, only the bottom node has a real value. Just modify the bottom value T old = p.value; p.value = value; return old; } // nowNode is the newly created bottom node. Index levels 0 to 31 int nodeLevel = (int) Math.round(random.nextDouble() * 32); SkipListNode<T> nowNode = new SkipListNode<T>(score, value, nodeLevel); //Initialize each layer and connect the nodes before and after each layer int level = 0; while (nodeLevel >= p.level) { for (; level <= p.level; level++) { insertNodeHorizontally(p.levelNode[level], nowNode.levelNode[level]); } p = p.pre; } // At this time, the number of layers of p is greater than that of nowNode before entering the cycle for (; level <= nodeLevel; level++) { insertNodeHorizontally(p.levelNode[level], nowNode.levelNode[level]); } this.length ++ ; if (this.maxLevel < nodeLevel) { maxLevel = nodeLevel; } return value; } private void insertNodeHorizontally(SkipListNode<T> pre, SkipListNode<T> now) { //Consider now first now.next = pre.next; now.pre = pre; //Consider the next node of pre if (pre.next != null) { pre.next.pre = now; } //Finally, consider pre pre.next = now; }

## delete

- Use the get method to find the element, and then release the reference relationship between the node attribute levelNode and the index of each layer

//SkipList public T remove(double score){ //Find the node corresponding to this key at the bottom SkipListNode<T> now = get(score); if (now == null) { return null; } SkipListNode<T> curNode, next; //Dereference the node attribute levelNode before and after each layer index for (int i = 0; i <= now.level; i++){ curNode = now.levelNode[i]; next = curNode.next; if (next != null) { next.pre = curNode.pre; } curNode.pre.next = curNode.next; } this.length--; //Update size and return the old value return now.value; }

### Use example

public static void main(String[] args) { SkipList<String> list=new SkipList<>(); list.printSkipList(); list.put(1, "csc"); list.printSkipList(); list.put(3, "lwl"); list.printSkipList(); list.put(2, "hello world!"); list.printSkipList(); System.out.println(list.get(2)); System.out.println(list.get(4)); list.remove(2); list.printSkipList(); }

## Welcome refers to an error in the text

## Reference articles

- Design and implementation of redis
- Skip list (skip list) Summary - java version
- Data structure and algorithm -- jump table