Implementing LinkedQueue

Here is the Queue interface:

public interface Queue<T> {
  void enqueue(T item);  // throws IllegalArgumentException if item is null
  void dequeue();        // throws NoSuchElementException if the queue is empty
  T front();             // throws NoSuchElementException if the queue is empty
  boolean isEmpty();
}

LinkedQueue<T> implements the Queue<T> interface with a singly linked list of nodes. The front of the queue is at the head, and the back is at the tail:

import java.util.NoSuchElementException;

public class LinkedQueue<T> implements Queue<T> {

  private Node<T> head;  // the front of the queue, or null when empty
  private Node<T> tail;  // the back of the queue, or null when empty

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

    Node(T value) {
      this.value = value;
    }
  }

  public LinkedQueue() {
    head = null;
    tail = null;
  }

  // enqueue, dequeue, front, and isEmpty go here
}

Solution

Not on a singly linked list. dequeue would remove the tail, which needs the node before it, and reaching that node means traversing from the head. On a doubly linked list, the tail can move to the previous node without a traversal, so every operation is $O (1)$ .

Solution

dequeue must also change tail when it removes the only item: afterwards head and tail are both null. enqueue must also change head when the queue is empty: afterwards head and tail both point at the new node.

Solution

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

public T front() {
  if (isEmpty()) {
    throw new NoSuchElementException();
  }
  return head.value;
}

public void dequeue() {
  if (isEmpty()) {
    throw new NoSuchElementException();
  }
  head = head.next;
  if (head == null) {
    tail = null;
  }
}

Solution

public void enqueue(T item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  Node<T> newNode = new Node<>(item);
  if (isEmpty()) {
    head = newNode;
  } else {
    tail.next = newNode;
  }
  tail = newNode;
}

Solution

All four are $O (1)$ in the worst case: each one reads or changes only head, tail, and at most one node.