Как хранится в памяти ArrayList

1️⃣ Как кратко ответить

ArrayList в Java хранит элементы в виде массива объектов. Он динамически изменяет размер, увеличивая емкость в полтора раза, когда текущий массив заполняется. Элементы хранятся последовательно, что обеспечивает быстрый доступ по индексу, но вставка и удаление элементов могут быть медленными из-за необходимости сдвига элементов.

2️⃣ Подробное объяснение темы

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

Как это работает

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

   • ArrayList использует массив для хранения своих элементов. Этот массив называется elementData.
   • Изначально, при создании ArrayList, выделяется массив с начальной емкостью (по умолчанию 10, если не указано иное).

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

   • Когда вы добавляете элемент в ArrayList, он помещается в первую свободную ячейку массива.
   • Если массив заполняется, создается новый массив, емкость которого увеличивается в 1.5 раза от текущей, и все элементы копируются в новый массив.

3. Доступ по индексу:

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

4. Вставка и удаление:

   • Вставка или удаление элемента в середине ArrayList требует сдвига всех последующих элементов, что может быть медленным (в худшем случае O(n), где n — количество элементов в списке).

Пример кода

import java.util.ArrayList;
​
public class ArrayListExample {
    public static void main(String[] args) {
        // Создаем ArrayList с начальной емкостью по умолчанию (10)
        ArrayList<String> list = new ArrayList<>();
​
        // Добавляем элементы в ArrayList
        list.add("Apple");  // Добавляем "Apple" в первую свободную ячейку
        list.add("Banana"); // Добавляем "Banana" в следующую свободную ячейку
        list.add("Cherry"); // Добавляем "Cherry" в следующую свободную ячейку
​
        // Доступ к элементу по индексу
        String fruit = list.get(1); // Получаем элемент с индексом 1 ("Banana")
​
        // Удаление элемента
        list.remove(0); // Удаляем элемент с индексом 0 ("Apple"), сдвигая остальные элементы влево
​
        // Выводим оставшиеся элементы
        for (String item : list) {
            System.out.println(item); // Выводит "Banana" и "Cherry"
        }
    }
}

Зачем это нужно

ArrayList используется, когда требуется динамическое изменение размера коллекции. Он удобен для случаев, когда нужно часто добавлять или удалять элементы в конце списка, а также когда требуется быстрый доступ по индексу. Однако, если требуется частая вставка или удаление элементов в середине списка, может быть более эффективным использовать другие структуры данных, такие как LinkedList.