Удаление последнего элемента из LinkedList в O (1) без итераторов (Java)

Question

Я пытаюсь реализовать свой собственный 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");
    }
}

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

Answer 1

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

Ваша попытка почти верна. В дополнение к изменению ссылки 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, вероятно, равен нулю), и после удаления список пуст.