Поиск элемента в списке пропуска

У меня возникли трудности с кодированием способа поиска элемента в списке пропуска.

Я пытаюсь реализовать это так, чтобы, если мы ищем элемент, а этот элемент не существует в списке, возвращалось следующее наибольшее значение; это сделало бы его идеальным для вставки. Однако, если элемент найден, верните этот элемент.

Я использую это для своего метода remove(T key); если мы найдем элемент, то удалим его. Если его нет в списке, throw new java.util.NoSuchElementException().

Хотя моя текущая реализация нормально работает для вставки, я обнаружил, что она не работает при поиске существующего элемента — вместо этого она получает следующее значение. (Технически это не должно работать для вставки, но работает).

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

Выше показано, как сейчас выглядит список пропуска.

Ниже представлена ​​структура списка пропуска, который я делаю. Левосторонние часовые — это узлы с нулевыми данными; у нас также есть фантомный узел, выступающий в роли головы; фантомная голова помогает нам отслеживать текущее количество уровней в списке пропуска. Структурная схема

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 есть в списке.


java list skip-lists
person Community    schedule 03.03.2015    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Я вижу здесь ряд проблем.

  1. Где вы на самом деле возвращаете значение? Я не вижу оператора возврата, хотя я предполагаю, что вы просто пропустили 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 — это предотвращает вызов getData() на несуществующем следующем узле, что может привести к исключению нулевого указателя. Также обратите внимание, как вы не проверяете, не уменьшаются ли нулевые значения. Это связано с тем, что вы сталкиваетесь с ним только в том случае, если его нет в списке, поэтому особый случай в начале поймает это нулевое значение при следующем выполнении цикла.

Вы также можете настроить, как он проверяет, равны ли значения. Я использовал .equals, но вы можете изменить его, чтобы использовать метод compare, в зависимости от того, как вы проверяете равенство.

person childofsoong    schedule 03.03.2015
comment
Это работает только для поиска элемента. Я хотел найти узел, если он был в этом списке, но если это не так, вернуть следующее по величине значение в списке; таким образом, я мог бы легко вставить новое значение прямо перед возвращаемым узлом. - person ; 03.03.2015
comment
Ах я вижу. Вы проверили правильность вызова метода compare? Я мог видеть, что это проблема, если вы хотели использовать >=, а не <=. - person childofsoong; 03.03.2015
comment
Способ выглядит так: compare(T a, T b), потом делаю a.compareTo(b). Я знаю, что если бы мы запустили search(3), то он дошел бы до точки, где он сравнивает 3.compareTo(5), который возвращает -1 правильно; Вот почему я не понимаю, почему это не работает. - person ; 03.03.2015
comment
Я тоже не уверен, что ваш метод работает. Если мы search(3), то в конечном итоге мы перейдем к 5, а затем к 5. Это неправильно. Он должен идти вниз по левому столбцу до тех пор, пока не появится data <= node.next.data. Ваш алгоритм сразу переходит к первому 5 на уровне 2. - person ; 03.03.2015