Array

An array is a composite data type, in the collection cathegory, that stores multiple values all of the same declared type, index accessed by a numeric array index which is computed at run time. By using a variable index, the array may be accessed for a not predetermined set of indices, during the run of the program.

The array has a lower bound, and an upper bound, beyond which it is illegal to access the array. The lower bound is in many programming languages fixed to either 0 (C and relatives) or 1 (Pascal and relatives), but the upper bound is always programmable. The size of the array is the distance from the lower bound to the upper bound and one extra. In all regular programming languages, the size of the array can be determined by the programmer at compile time or after. In many modern programming languages the size of the array may be computed and allocated at run time. In some programming languages also the lower bound may be specified by the programmer.

All values between (and including) the lower and the upper bound of the array may legally be accessed during the program run.

In most programming languages, arrays are accessed by using the array brackets [ and ], f.ex. in A[i], but exceptions are Rexx, instead using the dot operator ., such as in A.i, Ada which uses round parenteses A(i), and of course in the lisps which uses constructions like (ELT A n) for accessing and (SETA A n new_val) for setting (Interlisp) or (vector-ref A n) for accessing and (vector-set! A n new_val) for setting (Scheme).

Examples

C

We wish to open a text file and compute letter frequency

FILE *any_text;
/* declare array */
int frequency[26]; 
/* declare a computed index */
int ch; 
 
any_text = fopen ("a_text_file.txt", "rt");
 
/* init the freq table: */
for (ch = 0; ch < 26; ch++) 
    frequency[ch] = 0;
 
ch = fgetc(any_text);
while (!feof(any_text)) {
    if (is_a_letter(ch))
        /* if the char is a letter, then increase character slot in the freq table: */
        frequency[ch-'A'] += 1;
    ch = fgetc(any_text);
}

Computational metrics

Access is O(1), appending is O(1), and insertion is O(n).