Implement a queue using a linked list

Question

Implement a queue using a linked list.

I'm looking for a code review, optimizations and best practices.

public class QueueAsLinkedList<T> {

    private Node<T> front;
    private Node<T> rear;
    private int size;

    public QueueAsLinkedList() {} 

    private static class Node<T> {
        T item;
        Node<T> next;

        Node (T item, Node<T> next) {
            this.item = item;
            this.next = next;
        }
    }

    public void add(T item) {
        Node<T> node = new Node<T>(item, null);
        if (rear == null) {
            rear = node;
            front = node;
        } else {
            rear.next = node;
        }

        rear = node;
        size++;
    }

    public T remove() {
        if (front == null) {
            throw new NoSuchElementException();
        }
        T item = front.item;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        size--;
        return item;
    }

    public T peek() {
        if (front == null) {
            throw new NoSuchElementException();
        }
        return front.item;
    }

    public int getCount() {
        return size;
    }

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


    public static void main(String[] args) {
        QueueAsLinkedList<Integer> ll = new QueueAsLinkedList<Integer>();
        ll.add(1);   ll.add(2); ll.add(3);
        while (!ll.isEmpty()) {
            System.out.println(ll.remove());
        }
    }
}

Answer 1

• There is no point in having the constructor for Node require the 'next' node. It is never part of the constructor, in your code.

• The default constructor is useless code here. You may as well remove it, it does nothing.

• the method getCount should be called size to be conformant with other classes.

• I prefer when people use just one signal for the system state. In your code, you use size == 0 in some places to determine if the queue is empty, and in other places you use front == null

Otherwise the code looks functional, and neat.

Answer 2

Most coding conventions require that nested classes appear in a particular position within the enclosing scope - commonly at the bottom; see java.util.LinkedList. There's no one right answer to where it should be, but in the middle of the class is a bit odd.

You should probably be using isEmpty() as your state signal. That will cut down on the inconsistency issue raised by rolfl. Of course, to use isEmpty everywhere, you need to choose the correct implementation, and ensure that the modifications to the list are performed in a consistent order.

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

public T remove() {
    if (isEmpty()) {
        throw new NoSuchElementException();
    }
    T item = front.item;
    front = front.next;
    size--;

    if (isEmpty()) {
        rear = null;
    }
    return item;
}

add is really doing two different things; creating a new node, and inserting it into the list. These two chores should be made explicit

Node<T> createNode(T item) {
    return new Node<T>(item, null);
}

public void add(T item) {
    Node<T> node = createNode(item);
    add(node);
}

void add(Node<T> node) {
    if (isEmpty()) {
        front = node;
    } else {
        rear.next = node;
    }

    rear = node;
    size++;
}

If you are willing to jump through some extra hoops, you don't actually need the queue to contain two nodes -- one will suffice. The trick is implement a circular linked list. You still get O(1) insert and remove behavior.