### Topic 5 - Abstract data structures [HL]

# Multi-dimensional arrays

*This sections looks at characteristics of multi-dimensional arrays, some of its applications and how to work with them.*

## Review: What is an array?

An array is a data structure which stores a collection of elements. Each element can be identified by an *array index* or *key*.

*Figure 1: Illustration of one-dimensional array (By Jarkko Piiroinen, via Wikimedia Commons)*

In this illustration each element is represented by a box and its index is represented by the number on top. This also shows how in most programming languages an array index starts counting at 0.

## 5.1.4 Describe the characteristics of a two- dimensional array.

A two-dimensional array is simply an array in which each element contains another array. The following illustration shows this.

*Figure 2: Illustration of two-dimensional array (By Derrick Coetzee, via Wikimedia Commons)*

The common notation for accessing a two dimensional array is `array[i][j]`

, where `i`

is the index of element in the main array, and `j`

is the index for the element in the inner array. A useful and common example of such a two-dimensional array, is the representation of a table as follows.

arr[0][0] | arr[0][1] | arr[0][2] | arr[0][3] |

arr[1][0] | arr[1][1] | arr[1][2] | arr[1][3] |

arr[2][0] | arr[2][1] | arr[2][2] | arr[2][3] |

In such an example, the index `i`

would indicate the row and `j`

would indicate the column.

This idea can be extended to multi-dimensional arrays, where each array in an element contains further arrays.

## 5.1.5 Construct algorithms using two-dimensional arrays.

Tables have many applications and so do two-dimensional arrays. For instance, tables can be used to store the distances between cities.

*Figure 3: Distances between cities in New Zealand (Champion Freight)*

This could be used for calculating the total distance of a given path or to find the shortest route for a given tour.

Two-dimensional arrays are also often used for games, e.g. battleship or chess. Programming such a game is a good exercise to practise algorithmic thinking and the use of arrays!

**Further reading:** WikiBooks provides an excellent explanation of arrays and has good practice exercises for algorithms using two-dimensional arrays here.