4.2.1.1–4.2.1.2 - Data structures and multidimensional arrays (Java)

Choosing a data structure

A data structure organises related values so that a program can perform the operations its problem needs.

An attendance register needs one value per pupil per day; separate variables such as pupil1Monday quickly become unmanageable. An indexed structure lets the same loop process every pupil. A list of bookings may need frequent additions, whereas a fixed seating plan has a known number of positions. Choose by the meaning of the data, its size and the operations required, rather than using an array for every problem.

An array stores elements of one declared component type and accesses each element by an integer index. Java creates an array with a fixed length. For int[] visits = {4, 0, 7};, the legal indices are 0, 1 and 2: visits[2] is 7, and visits.length is 3. An access at index 3 is outside the array and causes an exception. A zero-length array is valid and contains no legal element index.

int[] visits = new int[3];   // three int elements, initially zero
visits[1] = 5;
int saved = visits[1];      // saved is 5

The variable holds a reference to the array object. int[] copy = visits; shares that same array; it does not duplicate the elements. Consequently copy[1] = 9; also changes the value seen through visits. Use a real copy when two independent collections are required.

Vectors and matrices as arrays

The number of indices needed to locate an element determines an array's dimensionality.

A one-dimensional array can represent a vector, such as three daily readings. A two-dimensional array can represent a matrix, such as pupils by days. More generally an $n$-dimensional array is indexed by an ordered tuple of $n$ integers; exchanging indices usually selects a different element.

int[][] attendance = {
    {1, 0, 1},
    {1, 1, 0}
};
int value = attendance[1][0];  // second row, first column: 1

This matrix has two rows and three columns. With zero-based indexing, (1, 0) means row 1 and column 0, not row 0 and column 1. Java implements a two-dimensional array as an array of row arrays. attendance.length is the number of rows and attendance[r].length is the length of row r. Rows can have different lengths: that is a jagged array, not a rectangular matrix. A rectangular-matrix algorithm must state or check its equal-row-length assumption.