Ring Buffer

A ring buffer trades flexibility for predictability — and wins whenever allocations are the bottleneck.

Context

Ring buffers use a fixed-size contiguous array to implement a queue with constant-time insertion and removal.

Compared to linked lists:

• no per-node allocation,
• better cache locality,
• trivial random access.

They trade fixed capacity for predictable performance.

Core idea

• allocate a fixed-size array
• maintain two indices:
  • head → next element to read
  • tail → next position to write
• advance indices using modulo arithmetic
• reserve one unused slot to distinguish full from empty

The buffer logically “wraps around” without moving data.

Implementation

This implementation is not thread-safe; concurrent access requires external synchronisation or a specialised design.

import java.nio.BufferOverflowException;
import java.nio.BufferUnderflowException;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class RingBuffer<T> implements Iterable<T> {
    private final int capacity;
    private final T[] buffer;
    private int head;
    private int tail;
    private int modCount;

    @SuppressWarnings("unchecked")
    public RingBuffer(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("Capacity must be greater than zero");
        this.capacity = capacity + 1;
        this.buffer = (T[]) new Object[this.capacity];
    }
    
    public void push(T item) {
        if (isFull()) throw new BufferOverflowException();
        buffer[tail] = item;
        tail = (tail + 1) % capacity;
        modCount++;
    }
    
    public T pop() {
        if (isEmpty()) throw new BufferUnderflowException();
        var data = buffer[head];
        buffer[head] = null;
        head = (head + 1) % capacity;
        modCount++;
        return data;
    }
    
    public T getFirst() {
        if (isEmpty()) throw new NoSuchElementException();
        return buffer[head];
    }
    
    public T getLast() {
        if (isEmpty()) throw new NoSuchElementException();
        return tail == 0 ? buffer[capacity - 1] : buffer[tail - 1];
    }
    
    public int size() { return (tail - head + capacity) % capacity; }
    
    public boolean isEmpty() { return size() == 0; }
    
    public boolean isFull() { return size() == (capacity - 1); }
    
    @Override
    public Iterator<T> iterator() { return new RingBufferIterator(); }
    
    private final class RingBufferIterator implements Iterator<T> {
        private int expectedModCount = modCount;
        private int current = head;
        private int remaining = size();
        
        @Override
        public boolean hasNext() {
          if (modCount != expectedModCount) throw new ConcurrentModificationException();
          return remaining > 0;
        }
        
        @Override
        public T next() {
            if (!hasNext()) throw new NoSuchElementException();
            var item = buffer[current];
            current = (current + 1) % capacity;
            remaining--;
            return item;
        }
    }
}