Gymterview
senior

Напишите минимальный неблокирующий ArrayList (всего четыре метода — add(), get(), remove(), size())

Реализация потокобезопасного ArrayList без использования блокировок. Подход — copy-on-write: при каждой модификации создаётся новая копия внутреннего массива, а ссылка на массив обновляется атомарно через volatile.

Код: copy-on-write ArrayList
class NonBlockingArrayList<T> {
    private volatile Object[] content = new Object[0];

    NonBlockingArrayList<T> add(T item) {
        return add(content.length, item);
    }

    NonBlockingArrayList<T> add(int index, T item) {
        if (index < 0) {
            throw new IllegalArgumentException();
        }
        boolean needsModification = index > content.length - 1;
        if (!needsModification) {
            if (item == null) {
                needsModification = content[index] != null;
            } else {
                needsModification = !item.equals(content[index]);
            }
        }
        if (needsModification) {
            final Object[] renewed = Arrays.copyOf(content, Math.max(content.length, index + 1));
            renewed[index] = item;
            content = renewed;
        }
        return this;
    }

    NonBlockingArrayList<T> remove(int index) {
        if (index < 0 || index >= content.length) {
            throw new IllegalArgumentException();
        }
        int size = content.length - 1;
        final Object[] renewed = new Object[size];
        System.arraycopy(content, 0, renewed, 0, index);
        if (index + 1 < size) {
            System.arraycopy(content, index + 1, renewed, index, size - index);
        }
        content = renewed;
        return this;
    }

    @SuppressWarnings("unchecked")
    T get(int index) {
        return (T) content[index];
    }

    int size() {
        return content.length;
    }
}

Принцип работы:

  • Чтение (get, size) — доступ к volatile-ссылке, без блокировки и копирования. Очень дёшево.
  • Запись (add, remove) — создание нового массива, копирование элементов, обновление volatile-ссылки. Дорого при большом массиве.

Ограничения:

  • Данная реализация не является строго потокобезопасной при конкурентных записях (два потока могут одновременно прочитать content, создать свои копии и последний перезапишет результат первого). Для полной потокобезопасности нужен CAS-цикл с AtomicReference или блокировка на запись, как в CopyOnWriteArrayList из JDK.
  • Аналог JDK — java.util.concurrent.CopyOnWriteArrayList, который использует ReentrantLock для защиты операций записи.

На собеседовании важно понимать trade-off: copy-on-write идеален для сценариев «много чтений, редкие записи» (списки подписчиков, кэши конфигурации), но плох для часто изменяемых списков.