时间戳

首页 > 解决方案 > 在没有迭代器的情况下从 O(1) 中的 LinkedList 中删除最后一个元素(java)

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

问题描述

我正在尝试实现我自己的 LinkedList，现在我的问题正在消除。我需要至少删除 O(1) 中的最后一个元素，但我不能这样做。在我看到的每一种情况下，人们都在从头到（最后一个 - 1）元素制作一个简单的循环，以这种方式删除尾部。但它具有 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");
    }
}

（这里我改变了我的尾巴，但我没有将前一个元素与那个尾巴连接起来，所以前一个元素仍然引用一个旧元素）

标签： javalinked-list

解决方案

看起来您的列表是一个双向链表，并且您确实引用了最后一个元素（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可能为空），并且在删除后列表为空。

推荐阅读