java - 在跳过列表中搜索元素

Question

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

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

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

虽然我当前的实现可以正常插入，但我发现它无法查找现有元素 - 相反，它将获取下一个值。 (从技术上讲，它不应该适用于插入，但它确实适用)。

********************* 跳过列表(大小 = 3) 级别:2(空), , , (5) 级别:1(空)、(3)、(4)、(5) **********************

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

下面是我正在制作的跳过列表的结构。左侧哨兵是数据为空的节点；我们还有一个虚拟节点作为头；幻像头帮助我们跟踪跳过列表中当前的级别数。 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)，返回的节点将为 5，即使 4 在列表中。

Answer 1

我在这里发现了很多问题。

1. 您实际上在哪里返回值？我没有看到任何 return 语句，尽管我猜你只是遗漏了 return node;在底部。

2. 您永远不会验证最终值是否确实是您正在寻找的值。我假设您需要某种方法来指示未找到值？

3. 如果您无法继续下去，您目前只是确定找到了该节点。

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

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 循环中的 null 条件 - 这会阻止您调用 getData()在不存在的下一个节点上，这将导致空指针异常。另请注意如何不检查空值是否下降。这是因为只有当它不在列表中时您才会遇到它，因此开始处的特殊情况将在下次循环执行时捕获该空值。

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