ARRAY

In computer science 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.
Some programming languages support array programming (e.g., APL, newer versions of Fortran) which generalizes operations and functions to work transparently over arrays as they do with scalars, instead of requiring looping over array members.
'Multi-dimensional arrays' are accessed using more than one index: one for each dimension.
Arrays can be classified as ''fixed-sized arrays'' (sometimes known as ''static arrays'') whose size cannot change once their storage has been allocated, and 'dynamic arrays', which can be resized.

Contents

Properties

Applications

Indexing

Index of the first element

Multi-dimensional arrays

Array system cross-reference list

See also

'External' link

Properties

Fixed-size arrays permit efficient (constant time, O(1)) random access. They are compact data structures, having a constant memory overhead. And, on CPUs which support caches, sequential iteration over an array has good locality of reference because its elements occupy contiguous memory locations. However, when an array is randomly accessed, for example when probing a hash table, locality of reference may be lost.

Applications

Because of their performance characteristics, arrays are used to implement other data structures, such as heaps, hash tables, deques, queues, stacks, strings, and VLists.
Some algorithms store a variable number of elements in part of a fixed-size array, which is equivalent to using dynamic array with a fixed capacity. See dynamic array for details.
Associative arrays provide a mechanism for array-like functionality without huge storage overheads when the index values are sparse. Specialized associative arrays with integer keys include Patricia tries and Judy arrays.

Indexing

Main articles: Index (information technology)

The valid index values of each dimension of an array are a bounded set of integers. Programming environments that check indexes for validity are said to perform bounds checking.

Index of the first element

The index of the first element varies by language. There are three main implementations: ''zero-based'', ''one-based'', and ''n-based'' arrays, for which the first element has an index of zero, one, or a programmer-specified value. The zero-based array was made popular by the C programming language, in which the abstraction of ''array'' is very weak, and an index ''n'' of an array is simply the address of the first element offset by ''n'' units. One-based arrays are based on traditional mathematics notation. ''n-based'' is made available so the programmer is free to choose the lower bound which is best suited for the problem at hand.
There is a list of programming languages at the end of the article.
In 1982 Edsger W. Dijkstra wrote a document, Why numbering should start at zero.
Supporters of ''zero-based'' indexing often incorrectly criticise ''one-based'' and ''n-based'' arrays for being slower. However, a ''one-based'' or ''n-based'' array access can be optimized with common subexpression elimination or with a well-defined dope vector.

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:
:$mathbf\{A\}\; =$
egin{bmatrix}
1 & 2 & 3 \
4 & 5 & 6 \
7 & 8 & 9
end{bmatrix}

It is most common to index this array using the ''RC''-convention, where elements are referred in ''row'', ''column'' fashion or $A\_\{row,col\},$, such as:
:$A\_\{1,1\}=1,\; A\_\{1,2\}=2,\; ldots,\; A\_\{3,2\}=8,\; A\_\{3,3\}=9,$
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.
In many applications, such as numerical applications working with matrices, we iterate over rectangular two-dimensional arrays in predictable ways. For example, computing an element of the matrix product 'AB' involves iterating over a row of 'A' and a column of 'B' simultaneously. In mapping the individual array indexes into memory, we wish to exploit locality of reference as much as we can. A compiler can sometimes automatically choose the layout for an array so that sequentially accessed elements are stored sequentially in memory; in our example, it might choose row-major order for 'A', and column-major order for 'B'. Even more exotic orderings can be used, for example if we iterate over the main diagonal of a matrix.

Array system cross-reference list

Programming language	Base index	Bound Check	Multidimensional	Dynamically-sized
Ada	n	checked	yes	init1
APL7	0 or 1	checked	yes	init1
assembly language	0	unchecked	no	no
BASIC	1	checked	no	init1
C	0	unchecked	yes2	heap3,4
C++5	0	unchecked	yes2	heap3
C#	0	checked	yes2	heap3,9
Common Lisp	0	checked	yes	yes
D	0	varies11	yes	yes
FreeBASIC	n	checked	yes	yes
Fortran	n	varies12	yes	init1,heap3
FoxPro	1	checked	yes	yes
IDL	0	checked	yes	yes
Java5	0	checked	no2	heap3
Lua	1	checked	no2	yes
MATLAB	1	checked	yes8	yes
Oberon-1	0	checked	yes	no
Oberon-2	0	checked	yes	yes
Pascal	n	checked	yes	varies10
Perl	n	checked	no2	yes
PL/I	n	checked
Python	0	checked	no2	yes
Ruby	0	checked	no2	yes
Scheme	0	checked	no2	no
Smalltalk5	1	checked	no2	yes6
Visual BASIC	n	checked	yes	yes
Windows PowerShell	0	checked	yes2	heap

# Size can be chosen on initialization/declaration after which it is fixed.
# Allows arrays of arrays which can be used to emulate multi-dimensional arrays.
# Size can only be chosen when memory is allocated on the heap.
# C99 allows for variable size arrays – however there is almost no compiler available to support this new feature.
# This list is strictly comparing language features. In every language (even assembler) it is possible to provide improved array handling via add on libraries. This language has improved array handling as part of its standard library.
# The class Array is fixed-size, but OrderedCollection is dynamic.
# The indexing base can be 0 or 1, but is set for a whole "workspace".
# At least 2 dimensions (scalar numbers are 1×1 arrays, vectors are 1×n or n×1 arrays).
# Allows creation of fixed-size arrays in "unsafe" code, allowing for enhanced interoperability with other languages
# Varies by implementation. Newer implementations (FreePascal and Delphi) permit heap-based dynamic arrays.
# Behaviour can be tuned using compiler switches. As in DMD 1.0 bounds are checked in debug mode and unchecked in release mode for efficiency reasons.
# Almost all Fortran implementations offer bounds checking options via compiler switches. However by default, bounds checking is usually turned off for efficiency reasons.

See also

★ Array slicing

★ Collection class

★ Parallel array

★ Set (computer science)

★ Sparse array

★

★

'External' link

★ NIST's Dictionary of Algorithms and Data Structures: Array