A simple example of implementing skip list in Java

Jump linked list is a randomized data structure. Based on parallel linked list, its efficiency can be compared with binary lookup tree (O (log n) average time is required for most operations), and it is friendly to concurrent algorithms.

Basically, the jump list is to add additional forward links to the ordered linked list. The increase is carried out in a randomized way, so the search in the list can quickly skip part of the list (hence its name). All operations were performed in logarithmic randomization time.

Implementation principle:

The structure of the jump table is: if the bottom layer has 10 nodes, then the upper layer of the bottom layer theoretically has 5 nodes, the upper layer theoretically has 2 or 3 nodes, and the upper layer theoretically has 1 node. Therefore, it can be seen from here that the number of nodes in each layer is 1 / 2 of the elements in the next layer, and so on. From here, we can see that when inserting, as long as we ensure that the number of elements in the upper layer is 1 / 2 of the number of elements in the next layer, our jump table can become an ideal jump table. So how can we ensure that the number of upper elements is 1 / 2 of the number of lower elements when we insert,? It can be solved simply by flipping a coin. Assuming that element X is to be inserted into the jump table, the bottom layer must be inserted with X. do you want to insert it in the lower layer? We hope that the number of elements in the upper layer is 1 / 2 of that in the lower layer, so we have a 1 / 2 probability to insert it into the lower layer. In this way, flip a coin. Insert it on the front, not on the back, and the lower layer is relative to the lower layer, We still have a 1 / 2 probability of insertion, so continue to flip coins, and so on. The probability of prime x inserting into the nth layer is (1 / 2) n times. In this way, we can insert an element into the jump table.

The first time I knew about the data structure of skip list was about a year ago (I may have been despised by countless compatriots when I said this sentence), but I didn't know how to implement it. What impressed me most at that time was an article on skip list - Implementation (Java), because the implementation of skip list in this article was the easiest to understand, At first, I had a further understanding of the skip table through this article, so I really want to thank the owner of this article. A year later, I found that my understanding of jump watch was blurred again, so this article came to my mind first. Read this article again today and implement the deletion method not given in it. Generics are added, but generics only use generics for value, and the string type in the original text is still used for key. Therefore, it is still relatively simple and limited. The reason why I posted it is to improve my understanding of skip list and serve as a memo. The link of the original text is as mentioned above. In fact, I don't know who the specific author of the original text is. I just want to say thank you silently here. Of course, if the original author thinks I have any offense or infringement, I will delete the post immediately.

For the definition and introduction of jump table, readers can refer to the original text. The only difference between the original code and the original text is, Here I give the deletion method not given in the original text (the original text actually refers to an English article, which gives the deletion method. I didn't find it until later. However, compared with the English article, the code is slightly redundant, and the deletion method implemented by myself is posted here). The implementation may be worse, so please criticize and correct!!!

1. The encapsulated class skiplistentry.java of each element (key value pair) in the hop table

2. Specific implementation of skip list (including addition, deletion, modification and query)

3 test

summary

The above is an example of how to implement a simple jump table in Java programming. I hope it will help you. Thank you for your support for this site!