Implement SkipList as a data structure using JavaScript

First let’s take a quick look at the JavaScript version of the code, as follows:

/** * author dreamapplehappy */ Const MAX_LEVEL = 16; const MAX_LEVEL = 16; /** * class Node{// data = -1; // the maxLevel attribute indicates that the current node is at the level of the entire hop table index maxLevel = 0; // if p is used to indicate the current node, level is used to indicate the level of the node in the entire index of the hop table; // p[level-n] = new Array(MAX_LEVEL); // p[level-n] = new Array(MAX_LEVEL); LevelCount = 1; levelCount = 1; levelCount = 1; // The head attribute is an instance of the Node class, pointing to the beginning of the entire list head = new Node(); Static randomLevel() {let level = 1; for(let i = 1; i < MAX_LEVEL; I++) {if(math.random () < 0.5) {level++; } } return level; } @param value */ insert(value) {const level = skiplist.randomlevel (); const newNode = new Node(); newNode.data = value; newNode.maxLevel = level; const update = new Array(level).fill(new Node()); let p = this.head; for(let i = level - 1; i >= 0; i--) { while(p.refer[i] ! == undefined && p.refer[i].data < value) { p = p.refer[i]; } update[i] = p; } for(let i = 0; i < level; i++) { newNode.refer[i] = update[i].refer[i]; update[i].refer[i] = newNode; } if(this.levelCount < level) { this.levelCount = level; Returns @param value * @returns {*} */ find(value) {if(! value){return null} let p = this.head; for(let i = this.levelCount - 1; i >= 0; i--) { while(p.refer[i] ! == undefined && p.refer[i].data < value) { p = p.refer[i]; }} if(p.reefer [0]! == undefined && p.refer[0].data === value) { return p.refer[0]; } return null; * @param value * @returns {*} */ remove(value) {let _node; let p = this.head; const update = new Array(new Node()); for(let i = this.levelCount - 1; i >= 0; i--) { while(p.refer[i] ! == undefined && p.refer[i].data < value){ p = p.refer[i]; } update[i] = p; } if(p.refer[0] ! == undefined && p.refer[0].data === value) { _node = p.refer[0]; for(let i = 0; i <= this.levelCount - 1; i++) { if(update[i].refer[i] ! == undefined && update[i].refer[i].data === value) { update[i].refer[i] = update[i].refer[i].refer[i]; } } return _node; } return null; PrintAll () {let p = this.head; while(p.refer[0] ! == undefined) { // console.log(p.refer[0].data) p = p.refer[0]; }}}Copy the code

If you look at the code above, it still doesn’t make sense; Don’t worry, below I will carefully explain the above code ideas

First, we define a Node class; The instance generated by this class has three attributes, data, maxLevel, and refer; Specific explanation can be seen in the code comments; Note the refer attribute, which is an array of length MAX_LEVEL and contains an index to another node. To get a sense of it, take a look at the picture below:

I don’t know if you can see the above picture a little bit better, if not, it doesn’t matter; Let’s keep going down here.

Next, we define a SkipList class. This class is the SkipList class we want to implement. SkipList instance properties levelCount and Head can be explained in the code comments;

Let’s take a look at the static method of the randomLevel class, which generates a value no greater than MAX_LEVEL; This value will generate a random index series as we add elements to SkipList; This random function is designed so that when we add elements to SkipList, the number of index nodes per level is approximately twice that of the previous level.

Let’s first look at SkipList’s find method. If you can understand the SkipList remove and insert methods, you should be able to quickly understand them. Let’s give it a try.

First we assign the whole list’s head pointer to p(here you might wonder why this.head is the whole list’s head pointer; We’ll cover this later when we cover the INSERT method. Then there are two loops, a for loop on the outside and a while loop on the inside; We can look at the picture below at this point:

The first thing we need to know is that the for loop starts at the top index of SkipList and runs from top to bottom; The while loop starts at a level’s index and loops left to right; Of course, when we say top to bottom and left to right, we’re referring to our diagram above.

Assuming that our SkipList is the one shown above, we now need to look for the value 9; What should we do? Take a look at our code above.

The levelCount of the index should be levelCount-1 (3). The levelCount of the index should be levelCount-1 (3). Then we enter a while loop that terminates if the next node in the hierarchy (denoted by p1) is not empty and the value of p1’s data is less than the value we are looking for.

We use L to represent the series of the current index, and p to represent the Node(or can be understood as a pointer) that is currently traversed. Then, when L =3, in the first while loop, P.reefer [3] represents the Node(1) of the third-level index. Since the loop conditions of the while are met, we perform another operation. P = p.reefer [I], which indicates that we are now traversing Node(1), or that the current pointer points to Node(1); Then we are ready for the next loop, but p. reefer! == undefined && p. return [I]. Data < value; Since p represents Node(1) and p. reefer [I] represents Node(15), the internal while loop terminates because p. reefer [I]. Data is greater than 9.

At this point, the outer for loop changes I to 2, and then p. reefer [I] represents the Node(1) above the second level index, satisfying the while loop, and then continues. We do not continue to describe the program running here. We can know that when p represents the Node(6) of the 0 level index, All cycles are over.

Then we need to make a judgment as to whether the next node at our current location is the value we need to find (why do we need to make a judgment? Because the condition of our loop is that the data value of the next node of the current node is less than the value we searched, if the loop ends, it means that the value of the next node of the current node is greater than or equal to the value, so we need to judge by this method). Return p.reefer [I] if so, or null if not.

We can use the following table to represent the notation 1 in the find function comment in this code, which should be more intuitive.

The SkipList insert and remove methods should quickly become clear to you if you understand the above description; We are not going to go through these two methods in as much detail as above; We’ll go through the implementation in general.

For the INSERT method, when inserting a data, we first generate a random level value that represents the level of the data index. Then we generate a newNode, newNode. Next we create an update array with a length of level; It contains nodes.

Next comes the familiar two-level loop. As you can see from the table above, the update array holds the node that the while loop terminates each time, as shown in the purple wirebox in Figure 3 above. We then run a for loop, and the code that follows is tricky: refer[I] for the new node to the next node and refer[I] for the update[I] node to the new node. When the loop is complete, We just inserted this data into the original SkipList. For a clearer picture of the process, see the picture below.

Then, we need to see if the current level is greater than SkipList’s maximum level, which is levelCount, and if it is, we need to update SkipList’s levelCount.

The remove method, this method is actually very similar to the remove method; The difference is that we first need to find the element to delete; If the element does not exist in SkipList, we cannot delete it; The element can only be deleted if it exists in SkipList; The so-called delete is to point the index of P(pre) to P(next) (where P(pre) indicates the previous node of P node at the same index level, and P(next) indicates the next node of P node at the same index level), so we delete this node; This process is illustrated in the figure below.

Finally, the printAll method, which prints out all the data we store in SkipList; Because the level 0 index holds our raw data. So far, we’ve covered the code part.