对 Java 的垃圾收集器如何工作感到困惑（节点 + 队列）

Question

所以我一直在尝试在 Java 中实现 LinkedList、Stack、Queue。

对于每个节点，我都使用一个节点 class 这样，现在我真的不想讨论我的实现方式，因为我知道有更好的方法可以做到，我只想专注于我的问题。

public class Node<E> {
    private E data;
    private Node<E> next;
    private Node<E> prev;

    public Node(E data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }

    public E getData() {
        return this.data;
    }

    public Node<E> getNext() {
        return this.next;
    }

    public Node<E> getPrev() {
        return this.prev;
    }

    public void setPrev(Node<E> prev) {
        this.prev = prev;
    }

    public void setData(E data) {
        this.data = data;
    }

    public void setNext(Node<E> next) {
        this.next = next;
    }
}

现在有了节点 class，我一直对垃圾收集器的工作方式感到困惑，所以假设这是我的队列 class

public class Queue<E> {
    private int size;
    private Node<E> head, tail;

    public Queue() {
        this.size = 0;
        this.head = this.tail = null;
    }

    public Queue(E data) {
        Node<E> temp = new Node<E>(data);
        this.tail = this.head = temp;
        this.size = 0;
    }

    public boolean enqueue(E data) {
        Node<E> temp = new Node<E>(data);

        if (this.head == null) {
            this.tail = temp;
            this.head = temp;
        } else {
            temp.setNext(this.head);
            this.head.setPrev(temp);
            this.head = temp;
        }
        this.size++;
        return true;
    }

    public E dequeue() {
        if (this.tail == null)
            throw new IndexOutOfBoundsException();
        else {
            E data = this.tail.getData();
            this.tail.setPrev(null);
            this.tail = temp;
            this.tail.setNext(null);
            this.size--;
            return data;
        }
    }

    public int getSize() {
        return this.size;
    }

    public E peak() {
        if (this.tail == null)
            throw new IndexOutOfBoundsException();
        else
            return this.tail.getData();
    }

    public boolean contains(E data) {
        if (this.head == null)
            return false;
        else {
            for (Node<E> cursor = this.head; cursor != null; cursor = cursor
                    .getNext()) {
                if (cursor.getData().equals(data))
                    return true;
            }
        }
        return false;
    }
}

现在我对垃圾收集器的工作方式感到困惑。我听说，它会清除所有未指出的引用。所以我在执行

的部分的出队 class 上不断收到 nullpointerexception

 this.tail.setNext(null);

现在，听说垃圾收集器工作，没有什么可以引用它，所以我想我的节点是这样设置的

       head          tail
 null<-[1]-><-[2]-><-[3]->null

每个节点都可以指向下一个和上一个，所以对于我的出列，我认为我必须做一些事情

1) 获取数据（很简单）

2) 获取指向前一个

的临时节点

 Node<E> temp = this.tail.getPrev()

3) 现在这里是我开始迷路的地方，为了不再引用每个节点，我必须摆脱所有指向它的指针，所以这意味着我必须将

this.tail.setPrev(null);

因为当我在那之后删除节点时，我不能回头删除那个引用

       head               tail
 null<-[1]-><-[2]-> null<-[3]->null
 <-[temp]-> ( equals node [2])

4) 将 tail 设置为指向临时节点，这是前一个节点

this.tail = temp;

不应该是这样的

       head   tail    
 null<-[1]-><-[2]->(this still points to [3])    null<-[3]->null

5) 但是第二个节点仍然指向[3]的内存地址，所以我继续

this.tail.setNext(null);

为了让我们不再引用任何记忆点，

       head   tail         will be deleted by GC
 null<-[1]-><-[2]->null      null<-[3]->null

然而，当队列中只剩下一个节点时，这部分给了我NullPointerException。

现在，我知道我在很多方面可能是错的，我还在学习，但我只是不确定我必须对每个节点做多少事情才能确保垃圾收集器得到它所以任何帮助可以，我需要将 prev 和 next 都设置为 null 吗？还是只有一个？等，所以任何帮助将不胜感激，谢谢 ;)

Answer 1

你真的不需要关心垃圾收集器是如何工作的。如果您的列表实现正确，那么垃圾收集器将正常运行。

您的NullPointerException将由逻辑错误引起。与垃圾收集无关。

队列中的头部和尾部引用应引用第一个和最后一个元素。

每个节点都应正确指向上一个和下一个元素。您的逻辑应该识别列表的开头和结尾，并且应该正确处理节点的插入和删除。

如果您从功能的角度来看是正确的，那么删除的节点将不会被任何东西引用，垃圾收集器将清理它。

专注于为边缘情况（空列表、单节点列表）编写单元测试并测试插入和删除操作。

一旦功能正确，垃圾收集就会正常工作。

编辑：

在一个长列表中，内部节点会有前一个和最后一个元素，但头和尾没有，所以你需要特殊的逻辑来处理删除它们。

如果列表只有一个元素，则头部和尾部相同，因此头部和尾部的特殊逻辑都适用于该节点。

Answer 2

您的代码中存在错误。它与垃圾收集器无关。你得到 NullPointerException 因为在你的示例中 this.tail 是 null 当队列中只有一个节点时。您只为一个节点分配 temp = this.tail.getPrev();，即 null。然后你分配this.tail = temp;。您将在下面找到 dequeue() 的正确实现。您不必这样做，但也许有些人会认为将所有内容设置为已删除节点中的 null 是一种很好的做法。

public E dequeue() {
        if (this.tail == null)
            throw new IndexOutOfBoundsException();
        else {
            E data = this.tail.getData();
            Node<E> temp = this.tail;

            this.tail = temp.getPrev();
            if ( this.tail == null ) { // if that was last node
                this.head = null;
                return data;
            }
            this.tail.setNext(null);

            temp.setPrev(null);
            temp.setNext(null);

            this.size--;
            return data;
        }
    }

在方法 enqueue() 中，您检查头部是否有空队列。但是在方法 dequeue() 中，您检查 tail 是否相同。这可能有点令人困惑。您可能应该检查两者是否 null。这是对你程序的额外测试。

构造函数中也存在错误。 this.size 应设置为 1 而不是 0。

public Queue(E data) {
        Node<E> temp = new Node<E>(data);
        this.tail = this.head = temp;
        this.size = 1;
    }

对 Java 的垃圾收集器如何工作感到困惑（节点 + 队列）

Confusion over how Java's Garbage Collector works (Nodes + Queue)

java

queue

garbage-collection

nodes