Array

An array, also known as a vector or list, is one of the simplest data structures in computer programming. Arrays hold a fixed number of equally sized data elements, generally of the same data type. Individual elements are accessed by index using integers, as opposed to an associative array. Most programming languages have arrays as a built-in data type. Since arrays (or more properly, array pointers or references) can themselves be members of arrays, arrays can be multi-dimensional; nevertheless, one- and two-dimensional arrays are the most common.

Arrays permit efficient (constant time, O(1)) random access but not efficient insertion and deletion of elements (which are O(n), where n is the size of the array). This is in contrast to linked lists, which have the opposite trade-off. Consequently, arrays are appropriate for storing data which will be accessed in an unpredictable fashion, and linked lists are best for data accessed sequentially.

The biggest drawback of the simplicity of arrays is the possibility of referencing to a non-existant element, for example using a negative index or asking for the 1000th element of a 100-elements array. In computer jargon, this is known as exceeding the array bounds. The result is, at best, a program working with incorrect data. At worse, the whole system can crash. This problem is particularly felt in the C programming language, which powerful syntax is unfortunately prone to this kind of errors. Other higher-level languages have built-in bounds checking, and will refuse indexing an array out of its permitted range.

A special use of arrays in some programming languages (such as C) is the use of one-dimensional character arrays to store strings. In C and C++ (where such arrays are known as "C strings"), the last element stores a null character ('\\0') which signifies the end of the string.

See also: Monge array, set, collection