Skip List - Eishaaya/GMRDataStructuresTest GitHub Wiki
A Skip List is a sorted list that increases search efficiency by having each node contain multiple neighbor references. Each node in the list is given a height or a collection of "Next" pointers that allow the structure to skip through values during searching. The structure is named Skip List since iterating through the list skips over lower-height elements.
To search through the list we start at the head element which is a dummy element that has the same height as the maximum element height in the list. The head element does not contain any data, it exists as a place to start searching. Then, starting from the highest link, we compare the next elements value to the value we are searching for. If the next element is null or its value is larger than we move down a link. If the next elements value is smaller we move to that element.
Nodes in a skip list choose their height upon creation with a random pattern such that the structure follows an ideal distribution with 50% of the nodes with height 1, 25% at height 2, 12.5% at height 3, and so on. This distribution exhibits an average of log2(n) running time for insertions, deletions, and lookups. An in-depth write-up on skip lists via Microsoft can be found here.
For this structure it is encouraged to start making use of C#'s interfaces. Implementing these interfaces will allow you to use other C# features and libraries on your data structures (such as LINQ). The most appropriate starting interface to implement for SkipList would be ICollection. Start by implementing this interface. You will notice that it will include most of the functions you were going to write.
Start at a minimum height of 1. Then, flip a coin. If it lands on heads, increase the height of the node and repeat. If it lands on tails, stop. This is the final height of the node.
The height of the node is random, but the Skip List must follow the log2(n) running time as described above. Nodes have a smaller chance of increasing height the taller they get (since landing on heads multiple times in a row becomes less probable). In order to limit the height of nodes in smaller lists, it is a good idea to have a maximum height a node can grow to be 'Head.Height + 1'. This allows the Skip List to generate larger height value nodes as the list grows but keeps the list from creating an over-sized nodes early on. It would be horrible if the first node in our list had a height of 42!
For inserting, generate a random height with the ChooseRandomHeight function. Start searching from the head node's highest link. Move down until you reach the correct height (the height generated by your ChooseRandomHeight function). Now create the node you want with the corresponding value passed in from the user as well as the correct height. At this point just insert how you would in a Sorted Doubly Linked List. Once you've inserted at the current height, move down and repeat. Make sure you are moving down to the correct node and that you connect the newly inserted nodes with thier bottom connections. (If a duplicate value is found, use one of the methods covered back in the BST chapter). The insertion is complete when the current level reaches -1.
For removal, search for the value to delete and when it is found have the current node link through the node to delete, then move down. Once the current level has moved down to -1 the removal is complete.
For Skip Lists, implement Unit Tests for the following:
- Adding
- Removing
- Searching
- Enumerating
- Take a look at our implementation if you are stuck.