Overview

In this chapter we shall be concerned with arrays of objects of given type, and with how to handle these arrays in a variety of applications in which the ordering of the elements of the array ( ie, of the individual objects) matters. We may wish, for example, to sort them according to some measure which will determine their order; or we may wish to shuffle them, or reorder them according to some other measure; or add to or subtract from their number while preserving the given order. The result can be a highly developed theory of data handling, much of which is of little relevance to numerical analysis. We dealt briefly with the sorting of an array in 14.4. Here, we shall consider more elaborate methods, but shall limit ourselves to the construction, manipulation and numerical applications of lists, both linear lists and circular lists. We shall not develop the beautiful theory of trees, useful though they are for certain applications.

First we note that an array is itself a list in the very limited sense that it has an order. If A is an array of n elements, each of type type, so that we can write

type A[n];

then the elements A[i], as we have seen, are ordered according to i = 0,1, , n ? 1. This ordering, however, merely reflects the order in which the various elements were inserted into...