Ниже приведена минимальная реализация неблокирующего ArrayList с методами add(), get(), remove() и size(). Эта реализация использует атомарные операции CAS (Compare-and-Swap) для обеспечения неблокирующих операций.
import java.util.concurrent.atomic.AtomicReferenceArray;
public class NonBlockingArrayList<T> {
private static final int DEFAULT_CAPACITY = 16;
private AtomicReferenceArray<T> array;
private AtomicInteger size;
public NonBlockingArrayList() {
this(DEFAULT_CAPACITY);
}
public NonBlockingArrayList(int capacity) {
array = new AtomicReferenceArray<>(capacity);
size = new AtomicInteger(0);
}
public void add(T element) {
int index = size.getAndIncrement();
if (index >= array.length()) {
// Увеличение размера массива при нехватке места
int newCapacity = array.length() * 2;
AtomicReferenceArray<T> newArray = new AtomicReferenceArray<>(newCapacity);
for (int i = 0; i < array.length(); i++) {
newArray.set(i, array.get(i));
}
array = newArray;
}
array.set(index, element);
}
public T get(int index) {
if (index < 0 || index >= size.get()) {
throw new IndexOutOfBoundsException();
}
return array.get(index);
}
public T remove(int index) {
if (index < 0 || index >= size.get()) {
throw new IndexOutOfBoundsException();
}
T removedElement = array.get(index);
for (int i = index; i < size.get() - 1; i++) {
T nextElement = array.get(i + 1);
array.set(i, nextElement);
}
array.set(size.get() - 1, null);
size.decrementAndGet();
return removedElement;
}
public int size() {
return size.get();
}
}
В этой реализации используются классы AtomicReferenceArray и AtomicInteger для обеспечения атомарного доступа к массиву и размеру списка соответственно. AtomicReferenceArray предоставляет атомарные операции чтения и записи элементов массива.
Метод add() добавляет элемент в список. Если внутренний массив заполнен, происходит его увеличение в два раза. Метод get() возвращает элемент по указанному индексу. Метод remove() удаляет элемент по указанному индексу и сдвигает остальные элементы, чтобы заполнить пустую позицию. Метод size() возвращает текущий размер списка.
Обратите внимание, что эта реализация не обрабатывает конкурентный доступ из нескольких потоков. Для поддержки конкурентного доступа и безопасности потоков требуется дополнительная работа, например, использование CAS-операций при реализации методов add(), remove() и size().
1606 вопрос-ответ по Java: https://github.com/DEBAGanov/interview_questions
Tелеграмм канал: https://t.me/DEBAGanov
Мое резюме: https://github.com/DEBAGanov
