在没有迭代器(java)的情况下从O(1)中的LinkedList中删除最后一个元素

Question

我正在尝试实现我自己的LinkedList，现在我的问题正在解决。我至少需要删除O(1(中的最后一个元素，但我做不到。在我看到的每一个例子中，人们都在做一个从head到(last-1(元素的简单循环，用这种方式去掉tail。但它具有O(n(复杂性。此外，我还发现java.util.中的LinkedList正在使用迭代器。所以我的问题是——我可以在不使用迭代器的情况下删除最后一个元素吗？或者我也需要实现迭代器类？这是我的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可能为null(，并且删除后列表为空，则可能需要添加另一个检查。