跳过列表是否可以有重复的元素？

Question

我知道一个skip-list是一个有序的数据结构，但它可以有重复的元素吗？或者应该是，如果你试图插入一个已经存在的元素，它将只返回指向预先存在元素的指针？

Answer 1

答案是“是的，一个跳过列表可以有重复的元素，但它不是必需的。”

你可以创建一个支持重复的跳过列表吗？绝对！您只需更新插入过程，以便如果您看到要查找的元素，则只需在元素后面插入元素即可。这与您如何拥有一个存储多个相等值的BST类似 - 只要插入过程总是向左或在找到相同元素时总是向右移动。

但是必须 skiplist总是允许重复？不，不需要，就像并非所有BST允许重复一样。

如果您使用跳过列表库，请参阅文档以查看它是否支持重复。如果你正在创建你自己的，那么随意创建它，然后记录下你的决定。