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

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?

• Are you asking for an explanation or a review? If the latter, of which codes, all of them?
– Mast
Commented Mar 2, 2017 at 12:42

## 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:

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.

• (+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. Commented Mar 2, 2017 at 18:22
• @Astrobleme - that's perhaps true, but then set them on the field declaration, and not again in the constructor Commented Mar 2, 2017 at 18:25