[PotatoPancakes]

> I remain unconvinced that skiplists cannot be better replaced in most cases with a good hash table/dictionary implementation.

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.

[dietrichepp]

You can typically insert into a skiplist in parallel with better performance than inserting into a balanced BST in parallel. So you may prefer a skiplist for concurrent write-heavy loads.

[jongjong]

Having implemented a SkipList and compared it to various binary tree implementations, my observation is that they're essentially equivalent in terms of performance for most operations. For insertion, my SkipList implementation was faster than most binary tree implementations but I found a Red-Black Binary Tree implementation which was faster.

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

[ignoramous]

> Perhaps without much advantage compared to, say, a balanced BST.

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.