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 a fixed amount of data which will be accessed in an unpredictable fashion, and linked lists are best for a list of data which will be accessed sequentially and updated often.
Another advantage of arrays that has become very important on modern architectures is that iterating through an array has good locality of reference, and so is much faster than iterating through (say) a linked list of the same size, which tends to jump around in memory. However, an array can also be accessed in a random way, as is done with large hash tables, and in this case there is no benefit.
Arrays also are among the most compact data structures; if you store 100 integers in an array, it takes only as much space as the 100 integers, and no more. Any pointer-based data structure, on the other hand, must keep its pointers somewhere, and these occupy space. This effect is magnified the smaller the data elements become; for example, an array of 100 characters usually takes 100 bytes, while on a 32-bit platform an aligned linked list of 100 characters takes 800 bytes, eight times as many. Conversely, for very large elements, the space difference becomes negligible.
A drawback of the simplicity of arrays is the possibility of referencing a non-existent element by using an index outside the range of valid indices. This is known as exceeding the array bounds. The result is, at best, a program working with incorrect data. At worst, the whole system can crash. This problem is particularly felt in the C programming language, the powerful syntax of which is unfortunately prone to this kind of error. Some other languages have built-in bounds checking, and will refuse to index an array outside of its permitted range.
Although useful in their own right, arrays also form the basis for several more complex data structures, such as heaps, hash tables, and vlists, and can be used to represent strings, stacks and queues. They also play a more minor role in many other data structures. All of these applications benefit from the compactness and locality benefits of arrays.
In the C programming language, one-dimensional character arrays are used to store null-terminated strings, so called because the end of the string is indicated with a special reserved character called a null character ('\0').
See also: Monge array, set, collection