Arrays

Arrays in general

An array is a fixed-size data structure where items can be accessed by their positions in the array.

An array is called ragged or jagged array if it is an array of arrays of different sizes.

The main advantage of using arrays is that they offer constant-time random access. This is because the memory is allocated for an array in such a way that the addresses of the array elements can be quickly computed [4]. On the other hand, the main disadvantage of using arrays is their fixed size. Once an array is created, its size cannot be changed.

Operation	Performance
Insert	`O(1)`
Search	`O(N)`

Arrays in Java

Arrays are first-class objects. An array object is only created in the heap when the array is initialized, not when it is declared. For example:

// a variable is created, but the array is not yet created
int[] a;

// now an array object is actually created in the heap
a = new int[] {1, 2, 3, 4};

// shortcut to initialize arrays
int[b] = {1, 2, 3, 4};

The differences between arrays and other containers are [5]:

Arrays offer a faster random access (as it is well-known for)
But array size is fixed
Arrays can contain either object references or primitive values, while containers can only hold object references.
Containers offer more utilities to work on them.

It is a compile-time error if the component type of the array being initialized is not reifiable [6].

// compile error
List<Integer>[] a = new List<Integer>[] {Arrays.asList(1), Arrays.asList(2)};

// a workaround to still guarantee type safe when using the array
List<Integer>[] a = (List<Integer>[]) new List[] {Arrays.asList(1), Arrays.asList(2)};

Arrays subject to covariant subtyping, i.e., S[] is a subtype of T[] if S is a subtype of T [7]. This is in contrast to the invariant subtyping used for the Java containers. Invariant subtyping means, for example, List<S> is not a subtype of List<T> even if S is a subtype of T.

Every array is associated with a Class object, and arrays with the same component type are associated with the same Class object [6].

int[] a1 = new int[]{1, 2};
int[] b1 = new int[]{3, 4};
assert a1.getClass() == b1.getClass();

Integer[] a2 = new Integer[]{1, 2};
Integer[] b2 = new Integer[]{3, 4};
assert a2.getClass() == b2.getClass();