SkipList java implementation
A SkipList S for a map M consists of a series of list {S0, S1, ……, Sh}. 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 Si+1 are chosen at random from the entries in Si, by picking each entry from Si, to also be in Si+1 with probability 1/2. That is, in essence, we “flip a coin” fro each entry in Si and place that entry in Si+1 if the coin comes up “heads”. Thus, we expect S1 to have about n/2 entries, S2 to have about n/4 entries and in general, Si to have about n/2i 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:
