### SkipList java implementation

A SkipList S for a map M consists of a series of list {S_{0}, S_{1}, ……, S_{h}}. Each list Si stores a subset of the entries of M sorted by increasing keys, plus entries with two sentinels keys denoted -∞ to +∞, where -∞ is smaller than every possible keys that can be inserted in M and +∞ is larger than every possible keys that can be inserted in M.

SkipLists ( aka JumpList) are an alternative representation of balanced trees (not binary) that provides approximate O(log n) access times with the advantage that the implementation is

straightforward and the storage requirement is less than a standard balanced tree structure.

Advantages:

- implementation is straightforward and easier than a typical balanced tree algorithm
- storage requirements are less than for typical balanced trees
- insertions and deletions do not require rebalancing
- supports insert,remove,find and join operations (especially useful for symbol table applications)

Disadvantages

- search time for insert and find is longer than for trees.
- depends on a random number generator which can mean difficult debug.

Insertion:

The entries in S_{i+1} are chosen at random from the entries in S_{i}, by picking each entry from S_{i}, to also be in S_{i+1} with probability 1/2. That is, in essence, we “flip a coin” fro each entry in S_{i} and place that entry in S_{i+1} if the coin comes up “heads”. Thus, we expect S_{1} to have about n/2 entries, S_{2} to have about n/4 entries and in general, S_{i} to have about n/2^{i} entries. As a consequence, we expect the height h of S to about log n.

Source: https://en.wikipedia.org/wiki/Skip_list

Source Code:

Github link: SkipList.java

Output: