What is a Skip List?
I have recently learned about a data structure that I was never taught in my university classes and I thought I would take the time to share it with you. A Skip List is a Probalibilistic Data Structure, which in essence means at the core of this data structure’s generation there is a completely random element. The Skip List random attribute allows for it to sort data quickly which causes low time run complexity with completely random data sets. This makes it an invaluable data structure to learn, not only for university studies but for job interviews and actual data that needs to be efficiently handled.
Let’s dive into what a Skip List is so that we can see why it is such an awesome data structure! Just like a search tree has branches a Skip List has layers that allow it to quickly access data. The bottom layer of a Skip List is a standard linked-list. Each time an element is inserted into the linked list the randomness algorithm the computer calculates coin-flip odds and on a heads, the element is also inserted on the layer above the bottom layer, and the computer calculates another set of coin-flip odds until a tails which will cease insertion. That might sound a little bit complicated… Here is a graphic that might explain it better than I can.
A neat ability of Skip Lists that you can leverage in the corporate settings or at least mention in a job interview if you happen to implement one of these is that you can trade space complexity for run-time complexity. This is to say that you can lower the threshold to make layers increase the number of layers and decrease runtime complexity.
I decided to test Skip Lists to see how fast they were compared to other fast data structures I know or have been taught. I wrote up / found implementations of an AVL Tree, a Doubly-Linked List, A Hash Table, and a standard Array and I tested them against the Skip List, and here’s what I found.
The color scheme of these graphs is Green for Doubly-Linked List, Blue for AVL Tree, Red for Hash Table, Cyan for Skip List, and Magenta for Standard List.
It’s very easy to see that the Doubly-Linked List and Hash table have much larger run time complexities and are skewing the plane of the graph so after removing them we get this graph generated; same color scheme.
Skip List in Cyan Blue had fantastic performance across the board it boasts really fast insertion times and yet remains lightweight enough to have great searching and access capabilities.
If you wish to read more about Skip Lists I can’t recommend enough this which is a deep dive into data structures done by Microsoft, but it contains a great section about Skip Lists that is really informative to read. If Skip Lists have really piqued your interest here is an MIT lecture that goes over Skip Lists!
Finally, if you're interested I will include a link to my public Github repository where I have uploaded all the code that generated these graphs if you would like to clone my repository and play around with skip lists.
