java 中 SLinkedList 中 removeFirst() 方法的实现

Question

我从一本书中得到了以下实现单向链表的代码。而且我不明白 removeFirst() 方法中的某些代码行，该方法从 LinkedList 中删除了第一个节点。

class ListNode{
    private String element;
    private ListNode next;

    public ListNode(){
        element = null;
        next = null;
    } 
    public ListNode(String s, ListNode n){
        element = s;
        next = n;
    }
    //Access method
    public String getElement(){
        return element;
    }
    public ListNode getNext(){
        return next;
    }
    //Modify method
    public void setNext(ListNode n){
        next = n;
    }
}

public String removeFirst(){
    if(head == null)
        return null;
    else{
        ListNode temp = head;
        head = head.getNext();
        temp.setNext(null);   //Which I don't understand, is it necessary?
        size --;
        return temp.getElement();
    }
}

看来temp.setNext(null);语句可以省略。那么为什么会在这里呢，跟java里面的垃圾回收有没有关系呢？由于我是 Java 的新手，有什么建议或想法吗？

Answer 1

这取决于链表的整个实现，你没有包含在你的问题中。但是，如果即使已从列表中删除，对象仍可能保留对节点的引用，则该行是必需的。

假设我们有一长串节点A -> B -> C -> ...。假设所有这些节点都已从列表中删除，但我们仍然保留对 A 的引用。如果所有节点仍然持有对下一个节点的引用，这将阻止所有节点被垃圾收集。只需将下一个节点设置为 null 即可确保只有 A 不能被垃圾回收。

很可能链表的实现do意味着可以保留对节点的引用。例如，Iterator 的许多实现持有对当前节点的引用。

考虑这段代码：

Iterator<String> iterator = list.iterator();
while (i.hasNext()) {
    if ("foo".equals(i.next())) {
        i.remove();
        break;
    }
}
// lots more code

此代码在列表中搜索 String "foo" 的第一次出现。如果找到，它会从列表中删除 "foo" 并中断循环。这样做的问题是 Iterator i 仍在剩余代码的范围内，并且仍然持有对节点的引用。如果 break 发生，该节点可能位于列表的中间。如果不将 next 设置为 null，这将阻止所有后续节点在 i 仍在范围内时被垃圾收集，即使列表已清除。

请注意，无论如何您通常都应该将迭代器设为循环的局部，就像这样

for (Iterator<String> i = list.iterator();;i.hasNext())

Answer 2

让我们假设，单个 linked 节点列表是：A --> B --> C --> D，头节点为 A。现在，让我们通过您的 removeFirst() 方法。当它被调用时，if(head == null) 条件不满足，因为我们的头节点 "A" 不是 NULL。然后执行else语句，
temp = head //将head引用放入临时变量
head = head.getNext(); //因为我们要删除第一个 Node，它是 head，所以我们将 head 设置为下一个节点（即 head --> next），即 Node "B"
现在，要删除 A（第一个节点），我们需要断开 A（前一个头）--> B（当前头）之间的连接，这将由
完成 temp.setNext(null); //所以linked列表变成了A B-->C-->D
然后当删除一个节点时，在下一条语句中它将 link 的大小减小 size--。

我认为我们还将临时引用设置为 NULL 作为 temp=NULL 以使已删除的节点符合垃圾收集条件。

java 中 SLinkedList 中 removeFirst() 方法的实现

Implementation of removeFirst() method in SLinkedList in java

java

garbage-collection

adt