Can a skip-list have duplicate elements?

Question

I know a skip-list is a sorted data structure, but can it have duplicate elements? Or should it be that if you try to insert an element that already exists it will just return the pointer to the preexisting element?

Answer 1

The answer is "yes, a skiplist can have duplicate elements, but it's not required to."

Can you make a skiplist that supports duplicates? Absolutely! You just update the insertion procedure so that if you see the element you're looking for, you just insert the element right after it. It's similar to how you can have a BST that stores multiple equal values - you just have the insertion procedure always go left or always go right when it finds an equal element.

But must a skiplist always allow duplicates? No, it doesn't have to, just the same way that not all BSTs allow for duplicates.

If you're using a skiplist library, consult the documentation to see whether it supports duplicates. If you're creating your own, feel free to build it however you'd like, and document your decision.