data-structures - 跳过列表可以有重复的元素吗？

Question

我知道跳过列表是一种排序的数据结构，但它可以有重复的元素吗？还是应该是，如果您尝试插入一个已经存在的元素，它只会返回指向预先存在的元素的指针？

Answer 1

答案是“是的，skiplist 可以有重复的元素，但不是必须的。”

你能制作一个支持重复的跳过列表吗？绝对地！您只需更新插入过程，这样如果您看到要查找的元素，您只需在其后面插入该元素。这类似于您如何拥有一个存储多个相等值的 BST - 您只需让插入过程在找到相等元素时始终向左或始终向右。

但是跳过列表必须总是允许重复吗？不，它不必，就像并非所有 BST 都允许重复一样。

如果您使用的是跳过列表库，请查阅文档以查看它是否支持重复项。如果您正在创建自己的，请随意构建它，并记录您的决定。