Simple Queue Implementation

Question

Purpose

As I've never implemented a queue, I decided to create a very simple implementation using a linked list approach.

Discussion

I create a singly linked list, using a private Node class that references some data and a previous Node, that will be used in my SimpleQueue class.

When enqueuing data, I check to see if the linked list is empty or not (by checking to see if the head of the list is null). If it's empty, point the head to a newly-created Node with the input data. If the list is not empty, I iterate through the list until I reach the end (i.e. the previous Node is null) and then I insert a newly-created Node.

When dequeuing, I throw an IllegalStateException if the queue is empty. If the queue is not empty, I set the new head of the queue to be the old head's previous value, and return the old head's data value.

Implementation

public class SimpleQueue<T> {
    private Node<T> head;

    private class Node<E> {
        private final E data;
        private Node<E> previous;

        public Node(E data, Node<E> previous) {
            this.data = data;
            this.previous = previous;
        }
    }

    public boolean isEmpty() {
        return this.head == null;
    }

    public void enqueue(T data) {
        Node<T> currentNode = this.head;
        Node<T> nodeToInsert = new Node<>(data, null);

        if (this.isEmpty()) {
            this.head = nodeToInsert;
        } else {
            while (currentNode.previous != null) {
                currentNode = currentNode.previous;
            }

            currentNode.previous = nodeToInsert;
        }
    }

    public T dequeue() {
        if (this.isEmpty()) {
            throw new IllegalStateException("Unable to dequeue from empty queue");
        }

        Node<T> currentNode = this.head;
        this.head = currentNode.previous;

        return currentNode.data;
    }

    public T peek() {
        if (this.isEmpty()) {
            throw new IllegalStateException("Unable to peek empty queue");
        }

        return this.head.data;
    }
}

Answer 1

            while (currentNode.previous != null) {
                currentNode = currentNode.previous;
            }

            currentNode.previous = nodeToInsert;

You can avoid this iteration if you track the location of the tail element.

            tail.previous = nodeToInsert;
            tail = tail.previous;

Of course, you have to maintain the tail in other places as well.

    private Node<T> tail;

    public void enqueue(T data) {
        Node<T> nodeToInsert = new Node<>(data, null);

        if (isEmpty()) {
            head = nodeToInsert;
        } else {
            tail.previous = nodeToInsert;
        }

        tail = nodeToInsert;
    }

But you no longer have to iterate this way.

Since both branches update tail, I moved that out of the if/else.

I notice that you use this. to specify object fields. That actually isn't necessary unless there is a conflict with a parameter or local variable. Of course, if you simply prefer it that way to make it obvious which variables are object fields, you can.

You can also update the tail when you dequeue to an empty queue, but you don't need to do so for functionality. It does allow the garbage collector to collect the node though.

Answer 2

Why "previous" ?

In common linked list implementations, nodes are chained together from left to right, and so the relation is usually labelled next. previous is commonly used in doubly-linked lists. Your implementation will be somewhat easier to read and look more natural to most programmers if you simply rename previous to next.

Borrow from the JDK

When trying to remove or get elements from an empty Queue, the JDK throws NoSuchElementException instead of the more generic IllegalStateException. When reinventing the wheel, consider looking at the JDK as a reference to borrow ideas. This will again make your code easier to read, and to use, if it's familiar.

Inner classes

The inner Node class doesn't need to reference anything in the enclosing class, so it can be a static. Not only it's good to clarify this aspect, it also improves performance by removing an unnecessary link.

Declare variables in the most limited scope

In enqueue, you declare currentNode up front, but it's only used later in the else block of a condition. Since it's not needed outside the condition, it would be better to move this declaration inside the else.