Primitive implementation of the Skiplist probabilistic data structure, written in C++. Originally designed for Dr. Afra Mashadi's CSS 342 class at UW Bothell during Winter 2021.
The skiplist achieves both search and insert functionality in O(log(n)) time. The basic idea is to create a grid-like linked structure, where each column represents a unique entry, and the heights of the columns are randomized upon insertion: Each time you create a new node, flip a coin. If you get heads, build another node above you, connecting it also to adjacent elements which achieve the same height, and so on. Thus, moving upwards along a column one step will bring you to a new row where, ostensibly, half of the entries 'did not make it.' This is how search—and insert—achieve O(log(n)) time.
This implementation is somewhat naïve and probably over-stores duplicate data by building multiple nodes for each block of height. Dynamic typing is also not implemented, so only integers may be used—though this may be an easy update. Another implementation might avoid instantiating so many duplicate nodes by having each node hold (instead of 4 pointers: left, right, up, down) 2 dynamically-sized column vectors of left- and right- pointers respectively, with the length of the vectors showing the overall height of the node, and the index of each pointer in the vector representing links at that height. The suite of tests, and the compilation scripts, are included as well.