1

到目前为止，我发现的所有跳过列表实现都使用键并将它们与值相关联。但是我需要的是一个跳过列表，我可以在其中在索引位置 i 处插入一个值，以便可以使用索引递增 1 来查询该索引 i 之后的所有值。

这里有一个澄清的小例子：

//pseudocode
//let skipList sk be a list of ints, containing 5 elements.

//insert 6 at index 3
sk.insert(3, 6);

//insert 5 at index 3
sk.insert(3, 5);

//get index 4
int value = sk.get(4);

现在value应该是 6，因为在索引 3 处插入了 5，所以值 6 向上移动了一个索引。

可以使用跳过列表构建这样的数据结构，请参阅此处的可索引跳过列表： http ://en.wikipedia.org/wiki/Skip_list

但我找不到实现。拥有这样的数据结构将非常有用，例如在大列表上有许多随机插入和访问的情况下。

4

2 回答 2

1

您发布的维基百科页面中似乎有一个实现链接：http: //code.activestate.com/recipes/576930/

它虽然是蟒蛇。

或者，采用现有的 C++ 实现并向其添加链接宽度并实现索引查找。

于 2013-01-17T13:56:44.787 回答
0

我在 C# 中实现了一个 skiplist 类，它有一个返回集合中第 k 个最大值的方法。它完全符合您的get方法所需。

但是，插入方法没有指定位置，因为它始终保持列表排序，因此位置由在现有值中的查找确定。

看看https://github.com/htoma/algorithms/blob/master/Algorithms/Algorithms/Sources/SkipLists/SkipList.cs，方法FindKLargestElement

于 2013-10-21T12:22:13.507 回答