Найти тему
DEBAGanov

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

Ниже приведена минимальная реализация неблокирующего 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