Skip Lists and Other Efficient Data Structures
If you are planning to store large and sparse tables efficiently, skip list could be an efficient solution. Titus Brown says he will implement it, if someone puts a gun on his head. We would rather call 911 and Sebastien says he will prefer few other data structures -
Wikipedia page on skip list provides good explanation of how it works.
A skip list is a data structure for storing a sorted list of items using a hierarchy of linked lists that connect increasingly sparse subsequences of the items. These auxiliary lists allow item lookup with efficiency comparable to balanced binary search trees (that is, with number of probes proportional to log n instead of n).
If that is not enough, please try this video (h/t: @sebhtml)
Other relevant links -
And do not forget Titus’ talk linked at the top of the commentary.
