Table or Array

The table or the array is most certainly the simplest and the most efficient data structure for numerous applications. An array can be simply defined as a fixed set (connected or contiguous) of memory where items of the same nature (more precisely, items having the same storage requirement) are sequentially stored and are accessible by one or several indices. The important point is that an array allows direct access to each and any of its elements. Indeed, if the array begins at the address a and if each item requires b words of memory to be stored, then the item of index i starts at the address a + ( i ? 1) b. This simple property means that the array is a convenient data structure, easy to use and hence, is used as a basic component in more sophisticated structures (trees, hash tables, grids, etc.).

Figure 2.1 shows an example of an array of length 6 containing integer values. Items 3 and 5 are not yet affected and thus, the corresponding values are undefined (symbolized by the ? sign).

Figure 2.1: An array of length 6

The intrinsic drawback of the array structure (besides the need to detect a possible overflow) is related to the static memory allocation it requires, before being used. In...