ArrayList

В прошлом уроке список рос сам, и размер ему никто не задавал. Но внутри ArrayList лежит обычный массив, а массив расти не умеет. Как же это устроено?

Вернёмся в гардероб. Шапки лежат на полке с ячейками. Когда свободные ячейки кончаются, гардеробщик берёт полку побольше, перекладывает на неё все шапки по порядку, а старую убирает. ArrayList поступает так же со своим массивом.

Но сначала посмотрим, что умеет список:

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> shelf = new ArrayList<>();
        shelf.add("hat");
        shelf.add("scarf");
        shelf.add("gloves");
        shelf.set(1, "cap");
        System.out.println(shelf);                   // [hat, cap, gloves]
        System.out.println(shelf.get(2));            // gloves
        System.out.println(shelf.contains("scarf")); // false
    }
}

Давайте разберём программу по строкам:

1. Три вызова add кладут "hat", "scarf" и "gloves" в конец списка по очереди. Они получают индексы 0, 1 и 2.
2. shelf.set(1, "cap") заменяет элемент с индексом 1: место "scarf" занимает "cap".
3. System.out.println(shelf) печатает [hat, cap, gloves].
4. shelf.get(2) читает элемент с индексом 2, то есть gloves.
5. shelf.contains("scarf") проверяет, есть ли в списке такой элемент, и отвечает false: шарф уже заменили. Элементы он сравнивает через equals.

Индекс за границей списка останавливает программу, как и у массива: shelf.get(3) бросит исключение IndexOutOfBoundsException.

Как растёт ArrayList

Внутри ArrayList лежит массив. Его длину называют ёмкостью списка, а число занятых ячеек — размером. Это разные числа: в массиве почти всегда есть запас.

Вот что происходит в JDK 25:

1. new ArrayList<>() пока не выделяет места под элементы.
2. Первый add создаёт массив на 10 ячеек.
3. Пока есть свободная ячейка, add кладёт элемент в неё, и это быстро.
4. Когда ячейки кончились, следующий add создаёт новый массив, примерно в полтора раза длиннее, копирует в него все элементы и добавляет новый.

Поэтому ёмкость растёт так: 10, 15, 22, 33, 49. Копирование случается редко, и в среднем добавление в конец остаётся быстрым. Как растёт ArrayList — частый вопрос на собеседовании.

Вставка в начало или в середину стоит дороже. add(0, x) кладёт элемент в начало и сдвигает все остальные на одну ячейку вправо. remove по индексу, наоборот, сдвигает влево все элементы после удалённого. В списке из миллиона элементов это до миллиона перекладываний.

Здесь картинка с полкой неточна. Настоящий гардеробщик переносит шапки у всех на глазах, а переменная shelf переезда не замечает. Она по-прежнему ведёт к тому же объекту ArrayList, а новый массив он держит внутри себя.

remove по индексу и по значению

У списка два метода remove:

• remove(int index) удаляет элемент с этим индексом;
• remove(Object o) ищет первый элемент, равный o по equals, и удаляет его.

В списке строк путаницы нет: shelf.remove("cap") может означать только второй метод. А в List<Integer> оба подходят, и здесь часто ошибаются:

List<Integer> nums = new ArrayList<>();
nums.add(7);
nums.add(5);
nums.add(1);
nums.remove(1);
System.out.println(nums); // [7, 1]
nums.remove(Integer.valueOf(1));
System.out.println(nums); // [7]

Разберём оба вызова:

1. В nums.remove(1) аргумент — int. Компилятор сначала ищет метод, который подходит без автоупаковки, и находит remove(int index). Удаляется элемент с индексом 1, то есть 5.
2. Integer.valueOf(1) — уже объект, поэтому вызывается remove(Object o). Он находит число 1 и удаляет его.

Частая ошибка

Из списка баллов хотели убрать число 70:

List<Integer> scores = new ArrayList<>();
scores.add(50);
scores.add(70);
scores.add(90);
scores.remove(70); // ✗

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 70 out of bounds for length 3

Программа компилируется, но останавливается при запуске. Java поняла 70 как индекс, а элемента с индексом 70 в списке из трёх нет. Чтобы удалить значение, передайте объект: scores.remove(Integer.valueOf(70)).

Главное

• ArrayList хранит элементы в массиве: add кладёт в конец, get и set читают и меняют по индексу, size и contains отвечают о содержимом.
• Когда массив заполнен, ArrayList создаёт новый, примерно в полтора раза длиннее (10, 15, 22, 33…), и копирует в него элементы.
• add(0, x) и remove по индексу сдвигают все элементы после этого места.
• У List<Integer> вызов remove(1) удаляет элемент с индексом 1, а число 1 удаляют через remove(Integer.valueOf(1)).