1
\$\begingroup\$

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?

\$\endgroup\$
1
  • \$\begingroup\$ Are you asking for an explanation or a review? If the latter, of which codes, all of them? \$\endgroup\$ – Mast Mar 2 '17 at 12:42
4
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ (+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. \$\endgroup\$ – Hungry Blue Dev Mar 2 '17 at 18:22
  • \$\begingroup\$ @Astrobleme - that's perhaps true, but then set them on the field declaration, and not again in the constructor \$\endgroup\$ – rolfl Mar 2 '17 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.