Can a missing list duplicate items?

Question

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

Answer 1

Answer: "Yes, a skipist can have repeating elements, but this is not required."

Can you make a skiplist that supports duplicates? Absolutely! You just update the insert procedure so that if you see the element you are looking for, you simply insert the element immediately after it. This is similar to how you can have a BST that stores several equal values ​​- you just have the insert procedure always go left or always go right when it finds an equal element.

But should a skipist always allow duplicates? No, this is not necessary, just like not all BSTs allow duplicates.

If you use the skiplist library, consult the documentation to see if it supports duplicates. If you are creating your own, do not hesitate to create them, no matter how you want, and document your decision.