Каква структура от данни се използва за реализиране на динамичен масив, подобен на ArrayList?

Динамичен масив, подобен на ArrayList в Java, реализиран на базата на обикновен масив. Основната идея е, че при достигане на текущия размер на масива, се заделя нов масив с увеличена капацитет (обикновено 1,5-2 пъти по-голям), и всички елементи се копират в него.

Това позволява ефективно добавяне на елементи без чести заделяния на памет, като същевременно се запазва бърз достъп по индекс.

Пример за опростена логика:

class SimpleArrayList<E> {
    private Object[] data;
    private int size = 0;

    public SimpleArrayList() {
        data = new Object[10];
    }

    public void add(E element) {
        if (size == data.length) {
            Object[] newData = new Object[data.length * 2];
            System.arraycopy(data, 0, newData, 0, data.length);
            data = newData;
        }
        data[size++] = element;
    }

    public E get(int index) {
        if (index >= size || index < 0) throw new IndexOutOfBoundsException();
        return (E) data[index];
    }
}