Массив и список
Массив (array) — фиксированный по размеру блок памяти, элементы лежат подряд. Это самая базовая структура данных, на которой строятся почти все остальные.
int[] nums = new int[5]; // сразу выделили место под 5 чисел
nums[0] = 10;
nums[2] = 30;
nums.length; // 5 — размер фиксирован раз и навсегдаСписок (ArrayList) — массив, который умеет расти. Если массив переполнился — ArrayList сам создаёт новый, больше, и копирует туда данные. Подробнее про ArrayList — в теме «ArrayList».
List<Integer> list = new ArrayList<>();
list.add(10); // не нужно заранее знать размер
list.add(30);Копнуть глубже
Почему доступ по индексу у массива мгновенный. Все элементы лежат подряд в памяти, и зная начальный адрес и размер одного элемента, можно вычислить адрес любого элемента простой формулой: адрес = начало + индекс × размер_элемента. Не нужно ничего перебирать — отсюда и O(1) для array[i].
Почему массив фиксированного размера, а ArrayList — нет. Массив — это просто непрерывный кусок памяти; чтобы его “увеличить”, память физически некуда расширить (соседние ячейки заняты чем-то другим). ArrayList решает это так: когда место кончается, выделяет новый, больший массив (обычно ×1.5) и копирует туда все элементы — поэтому добавление в конец иногда дороже обычного.
• почему доступ по индексу у массива — O(1) (если дошёл до 2-го слоя).