Java for Beginner

ArrayList: особенности и внутреннее устройство

ArrayList — это динамический массив, который является одной из наиболее часто используемых реализаций интерфейса List в Java. Он предоставляет упорядоченную коллекцию элементов и позволяет доступ к ним по индексу. В этом посте мы рассмотрим особенности и внутреннее устройство ArrayList.

Основные особенности ArrayList

Динамический размер:
В отличие от обычного массива, размер ArrayList может динамически изменяться. При добавлении элементов его емкость увеличивается автоматически.

Доступ по индексу:
ArrayList обеспечивает быстрый доступ к элементам по индексу. Операция получения элемента по индексу выполняется за постоянное время O(1).

Упорядоченность:
Элементы в ArrayList хранятся в том порядке, в котором они были добавлены.

Не синхронизированность:
ArrayList не является потокобезопасной коллекцией. Если необходимо использовать его в многопоточной среде, требуется внешняя синхронизация.

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

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

Массив для хранения элементов:
Внутри ArrayList используется массив Object[], называемый elementData, для хранения элементов.

private transient Object[] elementData;

Размер и емкость:
ArrayList имеет два важных параметра: size и capacity. size — это количество элементов, фактически находящихся в списке, а capacity — это размер внутреннего массива elementData.

Инициализация:
При создании ArrayList можно задать начальную емкость. Если она не указана, используется значение по умолчанию (обычно 10).

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = {};
    } else {
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    }
}

Если начальная емкость не указана:

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

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

Метод add добавляет элемент в конец списка. При добавлении элемента проверяется, хватает ли текущей емкости массива. Если нет, создается новый массив с увеличенной емкостью, и элементы копируются в него.

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // проверка емкости
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        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;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // увеличивается на 50%
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Получение элементов:

Метод get возвращает элемент по указанному индексу. Операция выполняется за постоянное время O(1).

public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

E elementData(int index) {
    return (E) elementData[index];
}

Удаление элементов:

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

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

#Java #Training #Medium #ArrayList

172 viewsДен, 05:36