Queue

A practical application of a linked list which shines in scenarios requiring FIFO ordering.

Context

A queue is a data structure that enforces FIFO (First-In, First-Out) ordering.

It exposes a minimal, intentionally constrained API:

• offer / enqueue → add to the end
• poll / dequeue → remove from the front
• peek → inspect the front element without removing it

When implemented with a linked structure and head/tail pointers, all core operations run in O(1) time.

Queues are a good example of a data structure that trades flexibility for predictable behaviour. When ordering matters more than random access, a queue is often the simplest correct tool.

Core idea

• Maintain two references:
  • head → next element to be removed
  • tail → last inserted element
• New elements are always appended at tail
• Elements are always removed from head
• Nodes store values and a pointer to the next node
• The queue never traverses internally — no scanning, no searching

This strict discipline is what guarantees constant-time operations.

Implementation

This problem is solved more efficiently with a Ring Buffer, which avoids per-node allocations.

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class Queue<T> implements Iterable<T> {
    private Node<T> head;
    private Node<T> tail;
    private int size;
    private int modCount;
    
    public void offer(T element) {
        if (size == 0) {
            head = tail = new Node<>(element);
        } else {
            tail.next = new Node<>(element);
            tail = tail.next;
        }
        size++;
        modCount++;
    }
    
    public T poll() {
        if (isEmpty()) return null;
        
        var temp = head.value;
        head = head.next;
        size--;
        if (head == null) tail = null;
        modCount++;
        
        return temp;
    }
    
    public T peek() { return isEmpty() ? null : head.value; }
    
    public boolean isEmpty() { return size == 0; }
    
    @Override
    public Iterator<T> iterator() { return new QueueIterator(); }
    
    private static final class Node<T> {
        private final T value;
        private Node<T> next;
        
        private Node(T value) { this.value = value; }
    }
    
    private final class QueueIterator implements Iterator<T> {
        private Node<T> current = head;
        private int expectedModCount = modCount;
        
        @Override
        public boolean hasNext() {
            if (modCount != expectedModCount) throw new ConcurrentModificationException();
            return current != null;
        }
        
        @Override
        public T next() {
            if (!hasNext()) throw new NoSuchElementException();
            var temp = current.value;
            current = current.next;
            return temp;
        }
    }
}