Что такое процедура в SQL?

ArrayList: реализация на основе динамического массива

Основная структура

ArrayList реализован с использованием обычного массива Java, который растёт динамически при необходимости.

Внутреннее устройство:

public class ArrayList<E> extends AbstractList<E> implements List<E> {
    // Основной массив для хранения элементов
    private Object[] elementData;
    
    // Текущее количество элементов
    private int size;
    
    // Стандартная начальная ёмкость
    private static final int DEFAULT_CAPACITY = 10;
    
    // Пустой массив для экземпляра с нулевой ёмкостью
    private static final Object[] EMPTY_ELEMENTDATA = {};
}

Как работает динамическое расширение

1. Инициализация:

public ArrayList() {
    // Начинаем с пустого массива
    this.elementData = EMPTY_ELEMENTDATA;
}

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

2. Добавление элемента:

public boolean add(E e) {
    // Убедиться что достаточно места
    ensureCapacityInternal(size + 1);
    // Добавить элемент в конец
    elementData[size++] = e;
    return true;
}

3. Расширение массива при нехватке места:

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {
        // Первое добавление: выделить DEFAULT_CAPACITY
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    // Нужно расширение если требуется больше чем есть
    if (minCapacity - elementData.length > 0) {
        grow(minCapacity);
    }
}

private void grow(int minCapacity) {
    // Старая ёмкость
    int oldCapacity = elementData.length;
    
    // Новая ёмкость = старая + (старая / 2)
    // Увеличиваем на 50%
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    // Если даже это не достаточно
    if (newCapacity - minCapacity < 0) {
        newCapacity = minCapacity;
    }
    
    // Защита от переполнения
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        newCapacity = hugeCapacity(minCapacity);
    }
    
    // Копируем старый массив в новый
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Пример работы

ArrayList<String> list = new ArrayList<>();

// Начальное состояние
// elementData = [] (пусто)
// size = 0
// capacity = 0

list.add("item1");
// Первое добавление:
//   Вызывается grow(1)
//   newCapacity = Math.max(10, 1) = 10
//   elementData = new Object[10]
//   elementData[0] = "item1"
//   size = 1

list.add("item2");
list.add("item3");
// ... item4-10 добавляются без расширения
// size = 10, capacity = 10

list.add("item11");
// Расширение:
//   oldCapacity = 10
//   newCapacity = 10 + 10/2 = 15
//   elementData = Arrays.copyOf(elementData, 15)
//   elementData[10] = "item11"
//   size = 11, capacity = 15

Операции с временной сложностью

// O(1) - добавление в конец (в среднем)
list.add("item");

// O(1) - получение по индексу
String item = list.get(5);

// O(n) - добавление в середину
list.add(5, "new item");  // сдвигаются все элементы после позиции 5

// O(n) - удаление из середины
list.remove(5);  // сдвигаются все элементы

// O(n) - поиск элемента
int index = list.indexOf("item");  // проходит весь список

Визуализация операций:

Добавление в конец: O(1)
[A][B][C][ ][ ]  <- есть место
[A][B][C][D][ ] <- просто добавляем

Добавление в середину: O(n)
[A][B][C][D][ ]
[A][X][B][C][D] <- сдвигаем всё после позиции

Удаление из середины: O(n)
[A][X][B][C][D]
[A][B][C][D][ ] <- сдвигаем всё влево

Особенности реализации

1. Использование Object[]:

Элементы хранятся в массиве Object[], а не прямо в массиве типа E.

// Внутри
private Object[] elementData;

// При добавлении
elementData[size++] = e;  // Object

// При получении требуется cast
@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];  // кастуем обратно
}

2. Быстрое расширение:

Для снижения количества переаллокаций используется 50% рост, а не удвоение:

10 элементов -> 15 (10 + 5)
15 элементов -> 22 (15 + 7)
22 элемента -> 33 (22 + 11)
...

Это баланс между памятью и частотой расширений

3. Итератор:

public Iterator<E> iterator() {
    return new Itr();
}

private class Itr implements Iterator<E> {
    int cursor;  // индекс следующего элемента
    int lastRet = -1;  // индекс последнего возвращённого
    int expectedModCount = modCount;
    
    public E next() {
        checkForComodification();
        int i = cursor;
        // ... проверки границ
        cursor = i + 1;
        return get(lastRet = i);
    }
    
    // Защита от ConcurrentModificationException
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

Сравнение с другими структурами

Когда ArrayList расширяется

ArrayList<Integer> list = new ArrayList<>(5);
// capacity = 5

for (int i = 0; i < 100; i++) {
    list.add(i);
    // Расширения происходят при:
    // size = 5 -> capacity = 7
    // size = 7 -> capacity = 10
    // size = 10 -> capacity = 15
    // size = 15 -> capacity = 22
    // ...
}

Оптимизация

Предвыделение памяти если знаешь размер:

// Плохо: много расширений
List<String> list = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
    list.add("item" + i);  // много расширений
}

// Хорошо: одно выделение
List<String> list = new ArrayList<>(10000);
for (int i = 0; i < 10000; i++) {
    list.add("item" + i);  // нет расширений
}

Вывод

ArrayList реализован на основе динамического массива:

• Структура: Object[] массив с двумя полями (elementData, size)
• Расширение: увеличивается на 50% когда нужно больше места
• Копирование: System.arraycopy() используется для переноса элементов
• Сложность: O(1) доступ, O(n) вставка/удаление в середину
• Оптимизация: предвыдели память если знаешь примерный размер

Это причина почему ArrayList отлично подходит для частого чтения и добавления в конец, но плохо для частых вставок в середину.