Реализация собственного MyArrayList по аналогии с ArrayList

50. Реализовать собственный MyArrayList

Условие задачи:
Необходимо реализовать динамический список MyArrayList<T> с поведением, похожим на ArrayList.

Требуемые методы:

add(T element);
get(int index);
remove(int index);
size().

При заполнении внутреннего массива список должен автоматически увеличивать его размер.

Код:

public class Main {

    public static void main(String[] args) {
        MyArrayList<String> list = new MyArrayList<>();

        list.add("Привет");
        list.add("Мир");
        list.add("Java");

        System.out.println(
                "Элемент по индексу 1: " + list.get(1)
        );
        System.out.println("Размер: " + list.size());

        list.remove(1);

        System.out.println("После удаления:");

        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }
}

Спойлеры к решению

Подсказки

💡 Элементы можно хранить во внутреннем массиве Object[].
💡 Поле size должно содержать фактическое количество элементов.
💡 Перед добавлением проверяй, достаточно ли места в массиве.
💡 При расширении можно увеличить вместимость примерно в 1.5 раза.
💡 После удаления сдвинь оставшиеся элементы влево.
💡 Проверяй индекс перед вызовами get() и remove().

Решение

public class MyArrayList<T> {

    private static final int DEFAULT_CAPACITY = 10;

    private Object[] elements;
    private int size;

    public MyArrayList() {
        elements = new Object[DEFAULT_CAPACITY];
    }

    public void add(T element) {
        ensureCapacity(size + 1);
        elements[size] = element;
        size++;
    }

    public T get(int index) {
        checkIndex(index);
        return elementAt(index);
    }

    public T remove(int index) {
        checkIndex(index);

        T removedElement = elementAt(index);
        int elementsToMove = size - index - 1;

        if (elementsToMove > 0) {
            System.arraycopy(
                    elements,
                    index + 1,
                    elements,
                    index,
                    elementsToMove
            );
        }

        elements[--size] = null;

        return removedElement;
    }

    public int size() {
        return size;
    }

    private void ensureCapacity(int requiredCapacity) {
        if (requiredCapacity <= elements.length) {
            return;
        }

        int newCapacity =
                elements.length + elements.length / 2;

        if (newCapacity < requiredCapacity) {
            newCapacity = requiredCapacity;
        }

        elements = Arrays.copyOf(
                elements,
                newCapacity
        );
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException(
                    "Index: " + index + ", size: " + size
            );
        }
    }

    @SuppressWarnings("unchecked")
    private T elementAt(int index) {
        return (T) elements[index];
    }
}

При добавлении элемент записывается в первую свободную ячейку. Если места недостаточно, внутренний массив расширяется.

При удалении элементы справа от указанного индекса сдвигаются влево, а последняя занятная ячейка очищается.

Временная сложность:

get() — O(1);
add() — амортизированно O(1);
remove() — O(n);
size() — O(1).