Array Basics

An array as a data structure

In Java, an array stores a fixed number of elements of one type. For algorithms, it is especially important that elements have positions — indexes from 0 to length - 1. This lets us access a required element directly by its position.

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

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

Access by a known index takes O(1): the length of the array does not affect the number of steps needed to read numbers[i]. This is one of the main array properties on which many algorithms are built.

What is fast and what requires traversal

If the index is already known, reading or replacing an element is direct:

numbers[2] = 99;

But if the index is unknown and you need to find a particular value, you usually have to inspect elements one by one. In the worst case, the whole array must be traversed, so ordinary linear search has complexity O(n).

int target = 30;
int index = -1;

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

An array's length does not change

After an array is created, its length is fixed. You can change the values stored in its cells, but you cannot append a new cell or remove an existing one in a way that makes the same array longer or shorter.

This makes an array predictable: the valid index range is known in advance, and an algorithm can rely on numbers.length as the size of the input.