Array

an array is a data structure consisting of a group of elements that are accessed by indexing. In most programming languages each element has the same data type and the array occupies a contiguous area of storage.

Most programming languages have a built-in array data type, although what is called an array in the language documentation is sometimes really an associative array. Conversely, the contiguous storage kind of array discussed here may alternatively be called a vector, list,^[1] or table.^[2

Multi-dimensional arrays

Ordinary arrays are indexed by a single integer. Also useful, particularly in numerical and graphics applications, is the concept of a multi-dimensional array, in which we index into the array using an ordered list of integers, such as in a[3,1,5]. The number of integers in the list used to index into the multi-dimensional array is always the same and is referred to as the array's dimensionality, and the bounds on each of these are called the array's dimensions. An array with dimensionality k is often called k-dimensional. One-dimensional arrays correspond to the simple arrays discussed thus far; two-dimensional arrays are a particularly common representation for matrices. In practice, the dimensionality of an array rarely exceeds three. Mapping a one-dimensional array into memory is obvious, since memory is logically itself a (very large) one-dimensional array. When we reach higher-dimensional arrays, however, the problem is no longer obvious. Suppose we want to represent this simple two-dimensional array:

It is most common to index this array using the RC-convention, where elements are referred in row, column fashion or , such as:

Common ways to index into multi-dimensional arrays include:

• Row-major order. Used most notably by statically-declared arrays in C. The elements of each row are stored in order.

1

2

3

4

5

6

7

8

9

• Column-major order. Used most notably in Fortran. The elements of each column are stored in order.

1

4

7

2

5

8

3

6

9

• Arrays of arrays. Multi-dimensional arrays are typically represented by one-dimensional arrays of references (Iliffe vectors) to other one-dimensional arrays. The subarrays can be either the rows or columns.

The first two forms are more compact and have potentially better locality of reference, but are also more limiting; the arrays must be rectangular, meaning that no row can contain more elements than any other. Arrays of arrays, on the other hand, allow the creation of ragged arrays, also called jagged arrays, in which the valid range of one index depends on the value of another, or in this case, simply that different rows can be different sizes. Arrays of arrays are also of value in programming languages that only supply one-dimensional arrays as primitives.

Tips :

 In a growing array, the amortized time complexity of all operations is O(1), except for removals and inserts into the middle of the array, which are O(n).

Because of their performance characteristics, arrays are used to implement other data structures, such as heaps, hash tables, deques, queues, stacks, strings, and VLists.