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?

• Mast: Are you asking for an explanation or a review? If the latter, of which codes, all of them?

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.

• Hungry Blue Dev: (+1) Good review. However I feel that explicitly supplying the default values shows the intent of the programmer and might be easier for a non-Java person to read.
• rolfl: @Astrobleme - that's perhaps true, but then set them on the field declaration, and not again in the constructor