![\"\"](\"https:\/\/www.kindsonthegenius.com\/wp-content\/uploads\/2020\/09\/Introduction-to-Skip-Lists-300x161.jpg\")
<\/p>\n
1. How Skip Lists Work<\/strong><\/h5>\nFirst of all, we define a skip list S for a map M consists of a series of lists {S0<\/sub>, S1<\/sub>,\u00a0 S2<\/sub>, . . . , Sh<\/sub>)<\/p>\nEach list Si<\/sub> in the set maintains a subset of the elements of M which is sorted in increasing order of the keys. Additionally, each list Si<\/sub> also stores two special keys, denoted as -\u221e and +\u221e where\u00a0-\u221e is smaller than all possible keys that can be inserted in m and +\u221e is greater than all possible keys that can be inserted in M. Additionally, the sublists satisfy the following conditions:<\/p>\n\n- List S0<\/sub> contains every possible item that can be stored in the map M (plus\u00a0 -\u221e and +\u221e).<\/li>\n
- For i = 1, . . . h-1, Si<\/sub> contains a randomly generated subset of the entries of Si-1<\/li>\n
- Lists Sh<\/sub> contains only\u00a0 -\u221e and +\u221e,<\/li>\n<\/ul>\n
<\/p>\n
2. Skip List Example<\/strong><\/h5>\nAn example of a skip list is given in Figure 1.0. In this skip lists 10 items are stored in addition to\u00a0-\u221e and +\u221e.\u00a0 S0<\/sub> is at the bottom of the lists with all the possible elements\u00a0 and as we move to the top of the list from S0<\/sub> to Sh<\/sub>, we could see that the number of items gradually reduces such that Si+ 1<\/sub> < Si<\/sub> and also Si+1<\/sub>\u00a0\u2282 Si<\/sub> (Si+1<\/sub> is a subset of Si<\/sub>)<\/p>\n <\/p>\n![\"Skip](\"https:\/\/www.kindsonthegenius.com\/wp-content\/uploads\/2020\/09\/Skip-Lists-1024x377.jpg\")
Figure 1.0: An example of a skip lists that stores 10 entries and maintains 6 sublists: S0<\/sub> to S5<\/sub> and a height of 6<\/figcaption><\/figure>\nThe insertion into a skip list is such that entries into sublist Si+1<\/sub> is randomly chosen from the entries of Si with a probability of 1\/2.\u00a0\u00a0This means that the number entries of S1<\/sub> is expected to be n\/2. Similarly, the number of entries of S2<\/sub> is expected to be n\/4 and so on.<\/p>\nGenerally, you can expect the number of entries in Si to be 1\/2i<\/sup>.\u00a0 This would then mean that the expected height of the skip list would be log n.<\/p>\nWe can therefore visualize skip lists as a 2-dimensional set of positions arranged horizontally in levels and vertically in towers. Each level is a sublist Si<\/sub> and each tower is a position for storing similar entries across the lists from bottom to top as can be seen in Figure 1.0. Maybe you can take some time to understand how it works<\/p>\n <\/p>\n
3. Skip Lists Traversal<\/strong><\/h5>\nWe can\u00a0 all the positions in skip list by using the following set of operations:<\/p>\n
\n- next(p): returns the position following p on the same level<\/li>\n
- prev(p): returns the position preceding\u00a0 p on the same level<\/li>\n
- below(p): returns the position directly below p in the same tower<\/li>\n
- above(p): returns the position directly above p in the same tower<\/li>\n<\/ul>\n
If however any of the operations mentioned above are carried out and the position does not exist, then the operation returns a null as a result<\/p>\n
<\/p>\n
4. Skip List Implementation<\/strong><\/h5>\nYou can implement a skip list using a linked structure that allows the four operations outlined above to each take constant time, O(1) given a skip list position p. Such linked list is a collection of doubly-linked list which of length h and\u00a0 are aligned at the towers. The towers are themselves also doubly-linked list.<\/p>\n
It is noteworthy that , in Java programming language, there is an implementation of the skip list data structure which is\u00a0 available in the ConcurrentSkipListMap class which provides method for get(), put() and remove, operations which are guaranteed to be performed at O(log n) times.<\/p>\n
Finally, The main advantage of the skip list is randomization, which makes them very simple and efficient.<\/p>\n
In the next lesson, we would then\u00a0 examine lookup and insertion into linked list.<\/p>\n
<\/p>\n
Check these Data Structure and Algorithms Tutorials<\/strong><\/h5>\nSkip Lists and How They Work<\/a><\/strong><\/p>\nPerfect Hashing \u2013 How it Works<\/a><\/strong><\/p>\nLinear Probing, Quadratic Probing and Double Hashing<\/a><\/strong><\/p>\nHashing With Open Addressing<\/a><\/strong><\/p>\nUniversal Hashing<\/a><\/strong><\/p>\nSearch Time Under Simple Uniform Hashing<\/a><\/strong><\/p>\nHash Tables \u2013 Hashing With Chaining<\/a><\/strong><\/p>\nIntroduction to Hash Tables and Direct Addressing<\/a><\/strong><\/p>\nRecurrences in Divide and Conquer Algorithm<\/a><\/strong><\/p>\nHow Bloom Filters Work<\/a><\/strong><\/p>\n
Each list Si<\/sub> in the set maintains a subset of the elements of M which is sorted in increasing order of the keys. Additionally, each list Si<\/sub> also stores two special keys, denoted as -\u221e and +\u221e where\u00a0-\u221e is smaller than all possible keys that can be inserted in m and +\u221e is greater than all possible keys that can be inserted in M. Additionally, the sublists satisfy the following conditions:<\/p>\n <\/p>\n An example of a skip list is given in Figure 1.0. In this skip lists 10 items are stored in addition to\u00a0-\u221e and +\u221e.\u00a0 S0<\/sub> is at the bottom of the lists with all the possible elements\u00a0 and as we move to the top of the list from S0<\/sub> to Sh<\/sub>, we could see that the number of items gradually reduces such that Si+ 1<\/sub> < Si<\/sub> and also Si+1<\/sub>\u00a0\u2282 Si<\/sub> (Si+1<\/sub> is a subset of Si<\/sub>)<\/p>\n <\/p>\n The insertion into a skip list is such that entries into sublist Si+1<\/sub> is randomly chosen from the entries of Si with a probability of 1\/2.\u00a0\u00a0This means that the number entries of S1<\/sub> is expected to be n\/2. Similarly, the number of entries of S2<\/sub> is expected to be n\/4 and so on.<\/p>\n Generally, you can expect the number of entries in Si to be 1\/2i<\/sup>.\u00a0 This would then mean that the expected height of the skip list would be log n.<\/p>\n We can therefore visualize skip lists as a 2-dimensional set of positions arranged horizontally in levels and vertically in towers. Each level is a sublist Si<\/sub> and each tower is a position for storing similar entries across the lists from bottom to top as can be seen in Figure 1.0. Maybe you can take some time to understand how it works<\/p>\n <\/p>\n We can\u00a0 all the positions in skip list by using the following set of operations:<\/p>\n If however any of the operations mentioned above are carried out and the position does not exist, then the operation returns a null as a result<\/p>\n <\/p>\n You can implement a skip list using a linked structure that allows the four operations outlined above to each take constant time, O(1) given a skip list position p. Such linked list is a collection of doubly-linked list which of length h and\u00a0 are aligned at the towers. The towers are themselves also doubly-linked list.<\/p>\n It is noteworthy that , in Java programming language, there is an implementation of the skip list data structure which is\u00a0 available in the ConcurrentSkipListMap class which provides method for get(), put() and remove, operations which are guaranteed to be performed at O(log n) times.<\/p>\n Finally, The main advantage of the skip list is randomization, which makes them very simple and efficient.<\/p>\n In the next lesson, we would then\u00a0 examine lookup and insertion into linked list.<\/p>\n <\/p>\n Skip Lists and How They Work<\/a><\/strong><\/p>\n Perfect Hashing \u2013 How it Works<\/a><\/strong><\/p>\n Linear Probing, Quadratic Probing and Double Hashing<\/a><\/strong><\/p>\n Hashing With Open Addressing<\/a><\/strong><\/p>\n Universal Hashing<\/a><\/strong><\/p>\n Search Time Under Simple Uniform Hashing<\/a><\/strong><\/p>\n Hash Tables \u2013 Hashing With Chaining<\/a><\/strong><\/p>\n Introduction to Hash Tables and Direct Addressing<\/a><\/strong><\/p>\n Recurrences in Divide and Conquer Algorithm<\/a><\/strong><\/p>\n How Bloom Filters Work<\/a><\/strong><\/p>\n\n
2. Skip List Example<\/strong><\/h5>\n
3. Skip Lists Traversal<\/strong><\/h5>\n
\n
4. Skip List Implementation<\/strong><\/h5>\n
Check these Data Structure and Algorithms Tutorials<\/strong><\/h5>\n