Основы массивов

Массив как структура данных

В Java массив хранит фиксированное количество элементов одного типа. Для алгоритмов особенно важно то, что элементы имеют номера — индексы от 0 до length - 1. Благодаря этому нужный элемент можно получить напрямую по его позиции.

int[] numbers = {10, 20, 30, 40};

int first = numbers[0];
int last = numbers[numbers.length - 1];

Доступ по известному индексу выполняется за O(1): длина массива не влияет на количество шагов, необходимых для чтения numbers[i]. Это одно из главных свойств массива, на котором строятся многие алгоритмы.

Что быстро, а что требует обхода

Если индекс уже известен, чтение или замена элемента выполняются напрямую:

numbers[2] = 99;

Но если известного индекса нет и нужно найти конкретное значение, обычно приходится проверять элементы один за другим. В худшем случае потребуется пройти весь массив, поэтому обычный линейный поиск имеет сложность O(n).

int target = 30;
int index = -1;

for (int i = 0; i < numbers.length; i++) {
    if (numbers[i] == target) {
        index = i;
        break;
    }
}

Длина массива не меняется

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

Это делает массив предсказуемой структурой: диапазон допустимых индексов известен заранее, а алгоритм может опираться на numbers.length как на размер входа.