When it comes to looking up 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 probability-based data structure. Each value stored in the list is stored in “towers” that have random heights.

Let’s back up 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 rook (for a single value) is determined by “tossing a coin” until tails. The number of times heads came up is the height of the specific tower.

The lowest level of the skip list (ie the base of all the rooks) 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 JumpList efficient, the elements are kept in order. This is important because when it comes time to search the list, we’ll 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 “tall” enough to reach this level, at which point we moved down one level from the current position of the tower (this avoids looking for the same values ​​at lower levels). However, if we are already at the bottom level, we can safely assume that the value is not in the skip list.

So how fast is a foreclosure listing? Very fast, when it comes to searching, it’s 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