[anfelor]

There is also a nice new datastructure called Zip Trees [1] which is isomorphic to skip lists in the sense that it performs exactly the same comparisons on insertion/deletion (but it can skip some redundant ones). I would expect zip trees to be faster than skip lists in practice.

[1]: https://arxiv.org/abs/1806.06726

[ajross]

Yeah, for those tempted in these directions, Zip trees seem like the clearly preferred tool. The variable-sized heap blocks of the skip list and the need for 4 pointers per entry (on average two doubly-linked list nodes) turn out to be real limitations in practice. At the end of the day, the only think skip lists really win on is code size.

For those not tempted and wondering if they should be: no, stick with your existing (red/black or AVL) balanced trees. They're clunkier and harder to explain, but they work just as well.

[mananaysiempre]

Unless you absolutely require deletion of a node specified by pointer, why would you include backlinks?

(Also, if you’re fine with resorting to randomized data structures, conventional treaps are quite good while being IMO easier to understand and code than either AVL or RB. The only reason I could imagine for not using them is adversarial input, although I’ve never seen an attack demostrated. Now that I’m reading the paper, zip trees seem quite nice and simple as well.)