Confusion over how Java's Garbage Collector wo

Question

This question already has an answer here:

• What is a NullPointerException, and how do I fix it? 12 answers

So I been trying to implement LinkedList, Stack, Queue in Java.

For each one i'm using a node class such that, now I don't really want to discuss how my implementation is since I am aware there are better ways to do it, I just want to focus on my question.

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;
    }
}

Now with the node class there, I keep getting mixed up on how the garbage collector works, so lets say this is my queue 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;
    }
}

Now I am getting how the garbage collector works confused. I have heard, it will clean up any references that don't get pointed too. So I keep getting nullpointerexception on my dequeue class on the part that does the

 this.tail.setNext(null);

now, hearing that for garbage collector to work, nothing can reference it, so I thought to myself my nodes are set up like this

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

where each node can point to next and to previous, so for my dequeue I think I have to do few things

1) get the data (that is easy)

2) get a temp Node that points to previous

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

3) now here is where I start to get lost, in order for each node to no longer be referenced, I have to get rid of all things pointer to it, so this means that I must set to null the

this.tail.setPrev(null);

since when I delete the node after that, I can't go backwards to erase that reference

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

4) Is set tail to point at temp node, which is what the prev node was

this.tail = temp;

no it should look like this

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

5) but the second node still points to the memory address of [3], so i continue to

this.tail.setNext(null); 

in order to make it so nothing at all references any spot of memory no longer in us,

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

However, THIS PART gives me NullPointerException when there is only one node left in queue.

Now, I know I may be wrong on a lot of this, I am still learning, but I am jsut not sure how much stuff I have to do to each node to make sure garbage collector gets it so any help will do, do i need to set both prev and next to null? or only one? etc, so any help will be appreciated, thank you ;)

Answer 1

There is bug in your code. It has nothing to do with Garbage Collector. You get NullPointerException because this.tail is null in your example when you have only one node in the queue. You assign temp = this.tail.getPrev(); which is null for one node only. Then you assign this.tail = temp;. Below you will find right implementation of dequeue(). You don't have to, but maybe some people would consider this a good practice to set everything to null in deleted node.

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;
        }
    }

In the method enqueue() you check head for an emtpy queue. But in the method dequeue() you check tail for the same. It might be little confusing. You should probably check both for null. It's additional test of your program.

There is also a bug in constructor. this.size should be set to 1 not 0.

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

Answer 2

You don't really need to care about how the garbage collector works. If your list implementation is correct then the garbage collector will function correctly.

Your NullPointerException will be caused by a logic error. Nothing to do with garbage collection.

Your head and tail references in the queue should reference the first and last elements.

Each node should correctly point to previous and next elements. Your logic should recognise the beginning and end of the list and should correctly handle insert and deleting of nodes.

If you get that right from a functional point of view, then deleted nodes won't be referenced by anything and the garbage collector will clean it up.

Concentrate on writing unit tests for edge cases (empty lists, one node lists) and test the operations insert and delete.

Once it is functionally correct, the garbage collection will work ok.

EDIT:

In a long list, inner nodes will have a previous and last element, but the head and tail don't, so you need special logic to deal with deleting them.

If the list has one element, the head and tail are the same, so both the head and tail special logic will apply to that one node.