Cold take:
I remain unconvinced that skiplists cannot be better replaced in most cases with a good hash table/dictionary implementation.
Also, most linked lists should actually be deques.
I remain unconvinced that skiplists cannot be better replaced in most cases with a good hash table/dictionary implementation.
Also, most linked lists should actually be deques.
Skiplists are ordered. Perhaps without much advantage compared to, say, a balanced BST. But Hash tables aren't ordered, so they aren't as good for storing data when preserving order is important.
> Also, most linked lists should actually be deques.
Yep, for almost all purposes, so long as using the extra memory for the reverse pointers isn't an issue. Deques are more flexible and much easier to work with (and especially to debug) than singly-linked lists. Not much of a take, I think a large proportion of developers would vehemently agree with you there.
A balanced BST comparatively does more work than a SkipList. Its cousin, SplayTrees, on the other hand, might give SkipList a run for its money.
Still, my SkipList was much faster with batch-deletion of contiguous records. This is because a SkipList does not require re-balancing after each individual deletion; once you've found a starting point and ending point (which has O(log n) time complexity), the deletion of an arbitrarily large chunk of a SkipList can be done in constant time.
Here is my implementation (Node.js/JavaScript) in case anyone is interested: https://www.npmjs.com/package/proper-skip-list