Arrays

Many computer programs require that quantities of identically typed data are processed. This is usually an indication that an array should be used. An array is a collection of data with each element of the same type. Initially we will assume that each element of an array is a simple type, for example an int. All of the elements of an array share a name, with the individual being addressed with an index pinpointing its location within that collection. In Java the first element of an array always has the index zero, so the first element of the array houses will be houses[0].

The array is in itself an abstraction, as in effect it is a collection of values being managed for us by the computer. The beauty of this is that we as programmers do not have to worry about how the computer is performing the task – all we need to do is provide the index and the computer calculates the rest for us.

In reality of course there is a concrete representation behind the abstraction. To illustrate this consider the case of an array of ten integers being held on a machine with two byte (16 bit) words. The illustration itself assumes that memory is held as an array of bytes – a common arrangement. (Note that some machines may regard memory as an array of words, and that some machines may require data to be aligned at word boundaries – this means that all word values must start at even addresses.)

array bytes

In order to allow the system to generate the address for each of the elements of the array, a calculation must be performed. This requires the following information:

  • The start address of the array
  • The index of the element
  • The size of each element.

For the array noted above, we can calculate the start address of the seventh element as follows:

start address + index of element * size of each element

substituting in actual values we have:

5A016  + 2 * 6 = 5AC16

Remember that the first element has array index zero, and that the seventh element has array index 6. The calculation of addresses within an array is usually performed by a mapping function.

Next: Stacks