If we wanted to maintain an ordered set of ints with a data structure that could insert, delete, find, and so on as quickly as possible, what data structure would you use?

An array of

Well, a very simple way to do that would be to use an array, and in terms of finding, if you use an array store, you can use dichotomy to find the element in order logn time, but arrays are less friendly to insert and delete, so it takes order logn time to find the target, The time required to perform the insert and delete actions is O(n), and the final time required is O(n) because both move elements. For example, for this array:

Insert element 3

The list

Another easy way to do this would be to use a linked list, which is relatively friendly in terms of insertion and deletion. The time required to insert and delete elements is O(1) when we find the target location. Note that I’m talking about the time required to insert and delete elements is O(1) when we find the target location.

However, the linked list is not friendly in search. It cannot use binary search like array, and can only be traversed one node at a time. Therefore, the total time complexity required by insertion and deletion is O(n) plus the time required by search.

If we can improve the efficiency of searching lists, so that the time complexity of searching lists is as close to O(logn) as possible, then lists will be a great choice.

Improve the search speed of linked list

Can the search speed of the list be improved?

For the list below

If we want to look for element 9, we’re going to have to go through eight nodes from the beginning to find element 9. Is there some strategy that will allow us to find element 9 within 5 iterations? Why don’t you take a minute to think about how to do that?

Because the elements are ordered, we can add some paths to speed up the search. For example,

This way, we only need to iterate 5 times to find element 9 (the red line is the path).

Can we speed up the search?

The answer is yes, add one more layer, so it only needs 4 times to find, it is like when we take the subway, to a station, there are fast line and slow line several routes, through the fast line + slow line collocation, we can get to a station faster.

Of course, you can add another layer,

Based on this method, for a linked list with N elements, we can take the form of ** (logn + 1) layer pointer path **, so that we can find a target element in the time complexity of O(logn). This data structure is also called skip list, and skip list can also be regarded as a deformation of linked list. But it has the function of binary search.

Insert and Delete

In the example above, we have 9 nodes and 4 layers, which is an ideal skip list, but as we insert/delete nodes into the skip list, the number of nodes on the skip list changes, which means that the number of layers on the skip list changes dynamically.

Here we have a problem, which is how many layers should the newly inserted node span?

This problem have been solved for us for sure, flip a coin to decide the new strategy is through the insert node across the number of layers: every time we have to insert a node, to flip a coin, if thrown out is positive, continued to cast, until a negative, statistical appeared in the process of the positive number, the number of times a node across the number of layers.

In this way, you can get as close to the ideal number of layers as possible. And you can think about why that is?

insert

For example, if we want to insert nodes 3 and 4, we know by flipping a coin that 3 and 4 span 0, 2 layers (the number of layers starts from 0), then the insertion process is as follows:

Insert 3, across layer 0.

Insert 4, spanning 2 levels.

delete

Now that we’re done inserting, let’s look at deletion, and deletion is a little bit easier, so if we want to delete 4, let’s just delete 4 and all the layers that it spans.

summary

Skip list insert and delete so far all talked about, summarize the skip list related properties:

(1). Each layer of the skip list is an ordered linked list.

(2). The search times of skip list is approximately the number of layers, the time complexity is O(logn), and the insertion and deletion are also O(logn).

(3). The bottom list contains all the elements.

(4). Skip list is a randomized data structure (the number of layers is determined by flipping a coin).

(5). The space complexity of skip list is O(n).

Skip lists vs binary lookup trees

One might say, well, you could do binary search trees, because the insertion, the deletion, the search of the search tree is also about order logn.

However, it is possible to have an extreme case of binary lookup trees where all the nodes will be biased to one side if the data inserted happens to be in order all the time. For example,

This connection structure will cause the search efficiency of the binary search tree to be O(n), which will greatly reduce the binary search tree.

Skip lists vs red-black trees

Red black is kind of a variant of a binary search tree, so red black is looking, inserting, deleting in order logn time, but if you’ve studied red black trees, red black trees are a lot more complicated than skip lists, but I’ve been beaten by red black trees. When choosing a data structure, it is sometimes necessary to consider the cost of learning.

In addition, when inserting or deleting nodes in a red-black tree, the balance of the red-black tree is maintained by adjusting the structure. Compared with skip list, which directly determines how many layers to be crossed by a random number, the cost of time complexity is higher than that of skip list.

Of course, a red-black tree is not necessarily worse than a skip list, and in some cases a red-black tree is a better choice, so choosing a data structure depends on the situation.

In general, skip lists are a good choice for maintaining an ordered set and wanting to do searches, inserts, deletes, and so on as quickly as possible. The data in Redis adopts skip list. Of course, RIDis also combines hash table and other data structures, and adopts a composite data structure.

The following code

package skiplist; Class Node{int value = -1; int level; Node[] next; Public Node(int value, int level) {this.value = value; this.level = level; this.next = new Node[level]; }} public class SkipList {// maxLevel = 16; // The header node acts as a helper. Node head = new Node(-1, 16); Int size = 0; // The number of layers in the current skip list, initialized to 1. int levelCount = 1; public Node find(int value) { Node temp = head;for (int i = levelCount - 1; i >= 0; i--) {
            while(temp.next[i] ! = null && temp.next[i].value < value) { temp = temp.next[i]; } // Check whether the element existsif(temp.next[0] ! = null && temp.next[0].value == value) { System.out.println(value +"Find successful");
            return temp.next[0];
        } else {
            returnnull; } // Insert a node that does not exist in the current skip list; // Insert a node with duplicate values. public void insert(int value) { int level = getLevel(); Node newNode = new Node(value, level); Update = new Node[level]; //update = new Node[level]; Node temp = head;for (int i = level - 1; i >= 0; i--) {
            while(temp.next[i] ! = null && temp.next[i].value < value) { temp = temp.next[i]; } update[i] = temp; } // Connect each layer of the inserted nodefor(int i = 0; i < level; i++) { newNode.next[i] = update[i].next[i]; update[i].next[i] = newNode; } // Determine whether the skip list needs to be updatedif (level > levelCount) {
            levelCount = level;
        }
        size++;
        System.out.println(value + "Insertion successful");
    }

    public void delete(int value) {
        Node[] update = new Node[levelCount];
        Node temp = head;

        for (int i = levelCount - 1; i >= 0; i--) {
            while(temp.next[i] ! = null && temp.next[i].value < value) { temp = temp.next[i]; } update[i] = temp; }if(temp.next[0] ! = null && temp.next[0].value == value) { size--; System.out.println(value +"Deletion successful");
            for (int i = levelCount - 1; i >= 0; i--) {
                if(update[i].next[i] ! = null && update[i].next[i].value == value) { update[i].next[i] = update[i].next[i].next[i]; }}}} // Prints all nodes public voidprintAllNode() {
        Node temp = head;
        while(temp.next[0] ! = null) { System.out.println(temp.next[0].value +""); temp = temp.next[0]; }} private intgetLevel() {
        int level = 1;
        while (true) {
            int t = (int)(Math.random() * 100);
            if (t % 2 == 0) {
                level++;
            } else {
                break;
            }
        }
        System.out.println("Current level =" + level);
        returnlevel; Public static void main(String[] args) {SkipList list = new SkipList();for (int i = 0; i < 6; i++) {
            list.insert(i);
        }
        list.printAllNode();
        list.delete(4);
        list.printAllNode();
        System.out.println(list.find(3));
        System.out.println(list.size + ""+ list.levelCount); }}Copy the code

If you think it’s good, you can give it a “like” so more people can see it. Thank you very much.

Finally promote my public number: helpless pain code farmers, articles will be the first in my public number, the public number has more than 100 original articles, looking forward to the attention of the hero communication.