Java.Multithreading.Write a minimal non-blocking ArrayList (only four methods – add(), get(), remove(), size()).

💪 Writing a non-blocking ArrayList is a tricky but fun task — because arrays require index-based coordination, which is much harder to do without locks than a linked structure like a stack.

But let’s take it step by step and aim for a minimal lock-free-ish dynamic array structure — using atomic operations only.

✅ Goal

Create a non-blocking ArrayList-like class with:

• add(T value) — append value
• get(int index) — read value
• remove(int index) — remove value at index
• size() — current element count

⚠️ Constraints & Assumptions

• We’ll use a fixed-capacity array for simplicity (no resizing).
• We’ll use AtomicReferenceArray<T> to store values.
• We’ll use AtomicInteger to track the current size.

This isn’t a full-blown dynamic ArrayList, but it demonstrates the principle of non-blocking coordination without synchronized.

🧱 Minimal Non-blocking ArrayList Implementation

import java.util.concurrent.atomic.*;

public class LockFreeArrayList<T> {
    private final AtomicReferenceArray<T> array;
    private final AtomicInteger size = new AtomicInteger(0);

    public LockFreeArrayList(int capacity) {
        array = new AtomicReferenceArray<>(capacity);
    }

    public boolean add(T value) {
        int index;
        do {
            index = size.get();
            if (index >= array.length()) return false; // Full
        } while (!size.compareAndSet(index, index + 1));

        array.set(index, value);
        return true;
    }

    public T get(int index) {
        if (index >= size.get()) throw new IndexOutOfBoundsException();
        return array.get(index);
    }

    public T remove(int index) {
        if (index >= size.get()) throw new IndexOutOfBoundsException();

        T oldValue;
        do {
            oldValue = array.get(index);
            if (oldValue == null) return null; // Already removed
        } while (!array.compareAndSet(index, oldValue, null));

        return oldValue;
    }

    public int size() {
        return size.get();
    }
}

✅ How It Works

• add() uses AtomicInteger to get the next available index without locking
• get() is safe due to AtomicReferenceArray
• remove() uses CAS to null out an index atomically
• size() is just a fast get()

🧪 Example Usage

public class Main {
    public static void main(String[] args) {
        LockFreeArrayList<String> list = new LockFreeArrayList<>(10);

        list.add("A");
        list.add("B");

        System.out.println(list.get(1));       // B
        System.out.println(list.remove(0));    // A
        System.out.println(list.get(0));       // null (removed)
        System.out.println(list.size());       // 2 (slots used)
    }
}

🧠 Notes

• This is non-blocking, but not wait-free.
• It does not shift elements after removal (unlike ArrayList) — it’s more like a sparse array.
• No resizing logic included — that’s very complex to do lock-free.