Удаление последнего элемента из linkedlist в o (1) без итераторов (java)

Я пытаюсь реализовать свой собственный LinkedList, и теперь моя проблема устраняется. Мне нужно удалить хотя бы последний элемент в O (1), но я не могу этого сделать. В каждом случае, который я просмотрел, люди делают простой цикл от головы до (последнего - 1) элемента, удаляя таким образом хвост. Но он имеет сложность O (n). Также я обнаружил, что LinkedList из java.util. использует итераторы. Итак, мой вопрос: могу ли я удалить последний элемент без использования итераторов или мне также нужно реализовать класс итераторов? это мой код метода popBack ():

private void popBack(){
    if(!isEmpty()) {
        --size;
        T temp = tail.info;

        //tail.next = null;
        //tail.prev.getNext();
        tail = tail.prev;
        System.out.println(temp);
    }
    else{
        System.out.println("OH SHI-, List is empty");
    }
}

(здесь я изменил свой хвост, но я не связал предыдущий элемент с этим хвостом, поэтому предыдущий элемент все еще относится к старому элементу)

Связанный список начинается с головы. Вам нужно будет пройти по цепочке, чтобы добраться до последнего звена.

user10452693 31.10.2018 12:30

Если у вас нет прямой ссылки на последний элемент в списке, вы не можете сделать это за O (1).

Andy Turner 31.10.2018 12:30
0
2
381
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Похоже, ваш список является двусвязным списком, и у вас есть ссылка на последний элемент (tail в вашем коде), что означает, что вы можете удалить последний элемент в O(1) time.

Ваша попытка почти верна. Помимо изменения ссылки tail для ссылки на tail.prev, вы должны установить ссылку next нового хвоста на null.

Никакие другие узлы списка не должны быть затронуты.

private void popBack(){
    if(!isEmpty()) {
        --size;
        T temp = tail.info;
        tail = tail.prev;
        tail.next = null;
        System.out.println(temp);
    }
}

Возможно, вам придется добавить еще одну проверку для случая, когда удаленный элемент был единственным элементом (в этом случае tail.prev, вероятно, равен нулю), и после удаления список пуст.

хорошо, конечно, я пробовал это, но когда я это делаю, я получаю NullPointerException

taciturno 31.10.2018 12:54

@Juicer вы удалили единственный элемент или ваш список содержит более одного элемента? Вы должны проверить этот tail != null, прежде чем пытаться установить для tail.next значение null (в случае, если вы удалили единственный элемент).

Eran 31.10.2018 12:56

@Juicer - Ответ Эрана мне кажется правильным. Пожалуйста, предоставьте MCVE, который точно показывает, что вы делаете, чтобы получить этот NullPointerException.

Stephen C 31.10.2018 13:18

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

taciturno 01.11.2018 15:44

Другие вопросы по теме