Implementation of removeFirst() method in SLinkedList in java

Question

I got the following code from one book for implementing a singly linked list. And I don't understand some lines of code in the removeFirst() method, which removes the first node from the 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();
    }
}

It seems that the statement temp.setNext(null); can be omitted. So why it is here, does it has anything to do with the garbage colletion in java. Since I am new to Java, any suggestions or ideas?

Answer 1

It depends on the entire implementation of the linked list, which you have not included in your question. However if it is possible for objects to hold a reference to a node even after if has been removed from the list, then the line is necessary.

Suppose we have a long chain of nodes A -> B -> C -> .... Suppose all of these nodes have been removed from the list, but that we still hold onto a reference to A. If all the nodes still held a reference to the next, this would prevent all of the nodes from being garbage collected. Simply setting the next node to be null ensures that only A cannot be garbage collected.

It is likely that implementations of a linked list do mean that references to nodes can be retained. For example, many implementations of Iterator hold a reference to the current node.

Consider this code:

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

This code searches a list for the first occurrence of the String "foo". If it is found, it removes the "foo" from the list and breaks from the loop. The trouble with this is that the Iterator i is still in scope for the remaining code and still holds a reference to a node. This node may be in the middle of the list if the break occurred. Without setting next to be null, this would prevent all subsequent nodes from being garbage collected while i is still in scope, even if the list is cleared.

Note that you should generally make an iterator local to a loop anyway, like this

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