在跳过列表中搜索元素

Question

我在编写一种在跳过列表中查找元素的方法时遇到了一些困难。

我正在尝试实现它，以便如果我们正在搜索一个元素并且该元素不存在于列表中，那么 return 下一个最大值；这将使它成为插入的理想选择。但是，如果元素位于，则 return 该元素。

我将它用于我的 remove(T key) 方法；如果我们找到该元素，则将其删除。如果它不在列表中，throw new java.util.NoSuchElementException().

虽然我当前的实现可以正常插入，但我发现它在查找现有元素时不起作用——相反，它将获取下一个值。（从技术上讲，它不应该用于插入，但确实如此）。

********************** SkipList (size = 3) Level: 2 (null), , , (5) Level: 1 (null), (3), (4), (5) **********************

以上是跳过列表当前的样子。

下面是我正在制作的跳过列表的结构。 Left-Hand 哨兵是数据为空的节点；我们还有一个虚拟节点充当头部；幻影头帮助我们跟踪跳过列表中的当前级别数。 Diagram of structure

private Node<T> search(T key) {
    Node<T> node = head;
    boolean found = false;

    while (!found) {
        while (compare(node.getNext().getData(), key) <= 0) {
            node = node.getNext();
        }
        if (node.getDown() != null) {
            node = node.getDown();
        } else {
            node = node.getNext();
            found = true;
        }
    }
    return node;
}

在当前状态下，如果我们尝试 search(4)，returned 节点将是 5，即使 4 在列表中。

Answer 1

我发现这里有很多问题。

您实际 return 在哪里计算值？我没有看到 return 语句，但我认为您只是在底部遗漏了一个 return node;。
您永远不会验证最终值确实是您要查找的值。我假设您需要某种方式来指示未找到值？
如果您无法下线，您目前只是认为您找到了该节点。

我认为您需要重新考虑一下算法。试试这个代码：

private Node<T> search(T key) {
    Node<T> node = head;
    boolean found = false;

    while (!found) {
        //special case to return a node containing null - indicates value not in list
        if (node == null) return new Node(null);
        //We found it!
        else if (node.getData().equals(key)) found = true;
        //Go to the next one over if it's not too high.
        else if (node.getNext() != null && compare(node.getNext().getData(), key) <= 0) node = node.getNext();
        //It was too high, so go down instead.
        else node = node.getDown();
    }
    return node;
}

注意在内部 while 循环中检查空条件 - 这可以防止您在不存在的下一个节点上调用 getData()，这将导致空指针异常。另请注意如何不检查空值是否下降。这是因为只有当它不在列表中时才会遇到它，所以开始时的特殊情况将在下次循环执行时捕获该空值。

您还可以调整它检查值是否相等的方式。我使用 .equals 但您可以将其更改为使用 compare 方法，具体取决于您如何检查相等性。

在跳过列表中搜索元素

Searching for element in Skip List

java

list

skip-lists