When it comes to finding data in C#, the .NET Framework offers some powerful data structures. However, one data structure that is not included is the skip list.
A Skip List is a data structure based on probability. Each value stored in the list is stored in “towers” that have random heights.
Let’s backtrack first. A jump list consists of a series of nodes. Each node contains several variables. The most important variable is the one that contains a reference to the value that is stored in the skip list. Then there are four more variables that point to other nodes (Left, Right, Up, Down).
You may have noticed that an exclude list is something like a linked list. That’s exactly right, skip lists in a series of LinkedLists stacked on top of each other. If you don’t know what a LinkedList is, don’t worry.
Now let’s talk about the properties of a C# skip list. A jump list has a random number of levels. The number of levels corresponds to the tallest tower on the list. The height of a tower (for a single value) is determined by “flipping a coin” until tails come up. The number of times heads came out is the height of the specific tower.
The lowest level of the skip list (ie the base of all towers) is the only level that contains all the values stored in the skip list. Any higher level is more likely to contain only some of the values.
Finally, the property that makes a Jump List efficient, the elements are kept in order. This is important because when it comes time to search the list, we will search from left to right, top to bottom.
If, while searching from left to right, we find a value that is greater than our “target” value (the one being searched for), then there are two possibilities. One is that the value tower was not “high” enough to reach this level, at which point we moved down one level from the tower’s current position (this avoids looking for the same values at lower levels). However, if we are already at the lowest level, we can safely assume that the value is not in the skip list.
So how fast is an exclusion list? Very fast, when it comes to searching it is faster than a normal List or Linked List. AC# Generic Skip List is therefore a powerful way to search through data.
For more data structures not included in the .NET Framework, visit Visual C# Kicks