dequeue() in Queue implememtation that uses a circular linked list

Question

I use a circular linked list to implement a queue, and it only holds one last (note that last.next links to the first, not null).

public class Queue<T> {

    private Node last;
    private int n;

    private class Node {
        T value;
        Node next;
        Node(T t, Node n) {
            value = t;
            next = n;
        }
    }

    public Queue() {
        last = null;
        n = 0;
    }

    public boolean isEmpty() {
        return n == 0;
    }

    public void enqueue(T item) {
        if (isEmpty()) {
            last = new Node(item, null);
            last.next = last;
        } else {
            Node tmp = new Node(item, last.next);
            last.next = tmp;
            last = tmp;
        }
        n++;
    }

   // other code
}

I think the correct way of dequeue() is :

public T dequeue() {
    if (isEmpty()) throw new NoSuchElementException();
    Node first = last.next;
    T t = first.value;
    if (last == first) {
        last = null;
    } else {
        last.next = first.next;
    }
    n--;
    return t;
}

This is because we should set last to null if there is one element.

However, the alternative way in following also works, why?

public T dequeue2() {
    if (isEmpty()) throw new NoSuchElementException();
    Node first = last.next;
    T t = first.value;
    last.next = first.next;
    n--;
    return t;
}

I call N times dequeue2() after N times enqueue(), and assert queue.last== null. To my surprize, the assertion passes. I think the last can never be null if I use dequeue2(). So, is the dequeue2() correct?

Answer 1

dequeue2

This method works because, when there's just one remaining item in the queue, the line:

Node first = last.next;

sets first to be the same as last (because, for a 1-sized queue last.next is a pointer to last).

In the other dequeue() you set last to be null when there's nothing left, but this does not make a difference, really (other than Garbage Collection) because the enqueue function checks the empty queue using n == 0 and not last == null

static inner class

Your Node class does not have any need for a back-reference to the Queue. It should be a static inner class private static class Node....... To do that, though, you need to make it generic too. Use a letter other than T to represent the generic class...

 private static class Node<U> {
    U value;
    Node<U> next;
    Node(U val, Node<U> n) {
        value = val;
        next = n;
    }
}

This saves a small amount of memory, but it is good practice. When you create the Node instances now, the code will change from:

private Node last;

to

private Node<T> last;

and you will add the <> diamond operator here:

Node<T> tmp = new Node<>(item, last.next);

Constructor:

Your constructor:

public Queue() {
    last = null;
    n = 0;
}

should just be:

public Queue() {
}

as you don't need to explicitly supply the default values.

General

Your code is neat, your variable names are not bad, and the use of generics is good.

As a learning exercise you should spend some time seeing if you can make it implement java.util.Queue interface (it's not easy - fair warning) because that will teach you a bit about what the actual Java Collections API offers.