关于 Java 链表上队列实现的线性时间和常量时间

Question

如果我维护the least added item的引用但不维护most recently added项目的引用，那么我将有常量时间"dequeue"和线性时间"enqueue"。 所以这是我在 Java 链表中实现队列的程序。我想问一下这个程序是否同时维护添加最少的项目和最近添加的项目？所以当我"dequeue"或"enqueue"时，这都是恒定的时间？谢谢！

add：我有点同意第一个答案所说的，所以我尝试了调试模式，它显示 oldlast 在上次更改后没有更新，所以它仍然在工作......但是从我从大学学到的参考理论来看，就像他说的那样，它不应该起作用。任何人都可以告诉我为什么它没有自动更新？（我的 Java 版本 1.8）

package tst;
public class linkedlsqueue {
    private class Node {
        String item;
        Node next;
    }
    Node first, last;
    public boolean isEmpty() {
        return first == null;
    }
    public void enqueue(String item) {
        Node oldlast = last;
        last = new Node();
        last.item = item;
        if (isEmpty()) {
            first = last;
        }
        else {
            oldlast.next = last;
        }
    }
    public String dequeue() {
        String item = first.item;
        first = first.next;
        if (isEmpty()) {
            last = null;
        }
        return item;
    }

}

Answer 1

是的，你是对的。 对于这两种情况，它都是恒定的。

最好同时记录链表的first和last。
有人称之为head和tail.

如果你只维护last或first中的一个，你必须通过迭代first来搜索另一个last以找到另一个，反之亦然 - 一个一个的元素，即 O（n）。

就像你在黑暗中一样。
你手握着绳子的一端，你想知道它会通向哪里。
除了追踪那根绳子，我想不出其他方法。 它需要 O（n） 来追踪。

不过我更喜欢使用数组[]。
使用数组，就像您拥有地图，太阳和超级门户（随机访问）。
但是，它不在问题的范围之内。

Answer 2

这个想法是正确的，但实现是错误的。

看看这个：

public void enqueue(String item) {
    Node oldlast = last;
    last = new Node();
    last.item = item;
    if (isEmpty()) {
        first = last;
    }
    else {
        oldlast.next = last;
    }
}

当你做oldlast = last时，你不会复制last，你只是last引用传递给oldlast。

在整个过程中，oldlast last是什么。同时，当您执行last = new Node()时，您可以重置last的值。

如果您只想排队，正确的方法可以像这样工作：

public void enqueue(String item) {
    Node newNode = new Node();
    newNode.item = item;
    if(isEmpty()){
        first = newNode; last = newNode;
        return;
    }
    this.last.next = newNode;
    this.last = newNode;
}

要正确复制元素，您应该执行以下操作：

Node oldlast = new Node();
oldlast.item = String(last.item);

希望有帮助。