Fetching latest commit…
Cannot retrieve the latest commit at this time.
|Failed to load latest commit information.|
Skip Lists, probably good. Skip lists are relatively new comers to the data structures scene (invented in the 90s). They differ from most data structures by being probabilistic rather than deterministic. Search, insertion and deletion times are expected to be O(log n) with a very high probability. Skip lists are normal linked lists with additional layers that enable queries to *skip* elements. They are much simpler than other O(log n) structures like Red Black Trees The skip list supports inserting multiple values for the same key. Values will be stored in a list attached to that key. Even a single value will be stored in a list Keys should implement <=> or you provide your own comparison block to the constructor The implementation still lacks range searches but they are on the todo list Here's a quick benchmark for insertion and search performance versus a normal array SkipList Inserting 16384 items 0.3022 s (18.44 microseconds) (~16x slower) Searching 16384 times 0.1931 s (11.786 microseconds) (~80x faster) Array Inserting 16384 items 0.01934 s (1.18 microseconds) Searching 16384 times 15.6141 s (953 microseconds) For this particular case a SkipList is ~16X slower than normal arrays for insertion of new values but they are like ~80x faster for searching