Как хранится индекс у ArrayList

Как хранится индекс у ArrayList

Это отличный вопрос про внутреннее устройство ArrayList, которое часто упускают при поверхностном изучении.

Структура данных ArrayList

ArrayList — это обертка над массивом. Основная идея:

public class ArrayList<E> extends AbstractList<E> implements Cloneable, Serializable {
    
    // Основной массив для хранения элементов
    transient Object[] elementData;
    
    // Размер — количество элементов, которые в использовании
    private int size;
    
    // Capacity — размер внутреннего массива
    // size != capacity!
    // Capacity >= size всегда
}

Как работает добавление элемента

public boolean add(E e) {
    // 1. Проверяем, есть ли место в массиве
    ensureCapacityInternal(size + 1);
    
    // 2. Добавляем элемент на позицию size
    elementData[size] = e;
    
    // 3. Увеличиваем size (не capacity!)
    size = size + 1;
    
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (minCapacity > elementData.length) {
        // Нужно увеличить capacity
        grow();
    }
}

Расширение массива (grow)

Когда заканчивается место, ArrayList автоматически увеличивает размер:

private static final int DEFAULT_CAPACITY = 10;
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private Object[] grow() {
    return grow(size + 1);
}

private Object[] grow(int minCapacity) {
    // Старый capacity
    int oldCapacity = elementData.length;
    
    if (oldCapacity > 0) {
        // Увеличиваем на 50% (oldCapacity >> 1 это деление на 2)
        int newCapacity = ArraysSupport.newLength(
            oldCapacity,
            minCapacity - oldCapacity,  // preferred growth
            oldCapacity >> 1             // 50% increase
        );
        
        // Создаем новый массив и копируем данные
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        // Первое добавление
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

Практический пример

public class ArrayListInternals {
    
    public static void main(String[] args) throws Exception {
        ArrayList<String> list = new ArrayList<>();
        
        // После создания:
        // size = 0
        // capacity = 0 (пустой массив)
        
        // Добавляем элементы
        for (int i = 0; i < 15; i++) {
            list.add("Item " + i);
            
            // Выводим внутреннее состояние
            printState(list);
        }
    }
    
    private static void printState(ArrayList<String> list) throws Exception {
        // Получаем размер через reflection
        Field sizeField = ArrayList.class.getDeclaredField("size");
        sizeField.setAccessible(true);
        int size = sizeField.getInt(list);
        
        // Получаем capacity (длину внутреннего массива)
        Field elementDataField = ArrayList.class.getDeclaredField("elementData");
        elementDataField.setAccessible(true);
        Object[] elementData = (Object[]) elementDataField.get(list);
        int capacity = elementData.length;
        
        System.out.printf("Added %d elements: size=%d, capacity=%d%n", 
            size, size, capacity);
    }
}

/* Вывод:
Added 1 elements: size=1, capacity=10      // Первое добавление — capacity=10 (DEFAULT_CAPACITY)
Added 2 elements: size=2, capacity=10
...
Added 10 elements: size=10, capacity=10
Added 11 elements: size=11, capacity=15     // Overflow! Расширяем на 50% (10 + 5)
Added 12 elements: size=12, capacity=15
...
Added 15 elements: size=15, capacity=15
Added 16 elements: size=16, capacity=22     // Overflow! Расширяем на 50% (15 + 7)
*/

Как получить доступ по индексу

public E get(int index) {
    // 1. Проверяем границы
    Objects.checkIndex(index, size);
    
    // 2. Просто возвращаем элемент из массива
    return elementData(index);
}

E elementData(int index) {
    // Прямой доступ к массиву — O(1)
    return (E) elementData[index];
}

Поэтому get(index) работает за O(1) — это просто обращение к массиву.

Важные отличия: size vs capacity

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);

// size = 3 (количество добавленных элементов)
System.out.println("Size: " + list.size());  // 3

// capacity = 10 (размер внутреннего массива)
// Как узнать capacity?
Field field = ArrayList.class.getDeclaredField("elementData");
field.setAccessible(true);
Object[] arr = (Object[]) field.get(list);
System.out.println("Capacity: " + arr.length);  // 10

Стоимость операций

Get by index:

E element = list.get(5);  // O(1) — просто обращение к массиву

Add at end:

list.add(element);  // O(1) amortized
// Иногда O(n) если нужно расширить (копировать все элементы)

Add in middle:

list.add(3, element);  // O(n) — нужно сдвинуть все элементы после позиции

Remove:

list.remove(5);  // O(n) — нужно сдвинуть элементы

Оптимизация для known size

// Если заранее знаешь размер — избегай расширений
ArrayList<String> list = new ArrayList<>(1000);

// Или используй ensureCapacity
list.ensureCapacity(1000);
for (int i = 0; i < 1000; i++) {
    list.add("Item " + i);  // Не будет расширений
}

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

*LinkedList быстрее если удаляешь с head/tail

Практический совет

// Если добавляешь много элементов
// Создавай с нужной capacity:
List<String> list = new ArrayList<>(expectedSize);

// Вместо:
List<String> list = new ArrayList<>();  // Будут расширения
for (...) {
    list.add(...);
}

Ключевые моменты:

1. ArrayList использует массив внутри — elementData[]
2. size != capacity — размер может быть меньше allocated памяти
3. Расширение на 50% — когда нужно больше места
4. Get(i) это O(1) — просто обращение к массиву
5. Add/Remove в середину это O(n) — нужно сдвигать элементы

АррейЛист выбирают за быстрый доступ по индексу, но не забывай про стоимость вставок/удалений в середину!