In computer programming, an array, also known as a vector or list, is one of the simplest data structures. Arrays hold a fixed number of equally-sized data elements, generally of the same data type. Individual elements are accessed by index using a consecutive range of integers, as opposed to an associative array. Some arrays are multi-dimensional, meaning they are indexed by a fixed number of integers, for example by a tuple of two integers; one- and two-dimensional arrays are the most common.Most programming languages have arrays as a built-in data type. Some programming languages (such as APL and J) generalize the available operations and functions to work transparently over arrays as well as scalars, providing a higher-level manipulation than most other languages, which require loops over all the individual members of the arrays.
1 Advantages and disadvantages
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). Linked lists have the opposite trade-off. Consequently, arrays are most 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 with insertions or deletions.
Another advantage of arrays that has become very important on modern architectures is that iterating through an array has good locality of referenceIn computer science, locality of reference sometimes also called the principle of locality is a concept which deals with the process of accessing a single resource multiple times. There are three basic types of locality of reference: temporal, spatial and, 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 tableIn computer science, a hash table is a data structure that speeds up searching for information by a particular aspect of that information, called a key''. If the information is a set of customer records, for example, the keys might include first name, lass, and in this case this is not a benefit.
Arrays also are among the most compact data structures; storing 100 integers in an array takes only 100 times the space required to store an integer, plus perhaps a few bytes of overhead for the whole array. Any pointerThis article is about the computer data type. For other meanings of pointer see pointer (disambiguation). In computer science, a pointer is a programming language datatype whose value is used to refer to ("points to") another value stored elsewhere in the-based data structure, on the other hand, must keep its pointers somewhere, and these occupy additional space. This extra space becomes more significant as the data elements become smaller. For example, an array of characterFor alternate meanings, see character. In computer terminology, a character is a unit of information that roughly corresponds to a grapheme, or written symbol, of a natural language, such as a letter, numeral, or punctuation mark. The concept also includes usually takes up one byte per character, while on a 32-bit platform, which has 4-byte pointers, an aligned doubly-linked list takes up nine bytes per character. Conversely, for very large elements, the space difference becomes a negligible fraction of the total space.
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 crashA crash in computing is a condition where a program (either an application or part of the operating system) stops performing its expected function and also stops responding to other parts of the system. Often the offending program may simply appear to fre (it is important to note that in cases where data integrity is critical, such as online banking, a crash may be preferable to working with incorrect data). This problem is particularly felt in the C programming languageThe C Programming Language Brian Kernighan and Dennis Ritchie, the original edition that served for many years as an informal specification of the language The C programming language is a low-level standardized programming language developed in the early, the powerful syntax of which is unfortunately prone to this kind of error. Some other languages as Java have built-in bounds checkingBounds checking is the name given to any method of detecting whether or not the index given lies within the limits of the array. For example, accessing index 25 on an array of size 10 would be caught by bounds checking as an invalid index, because it does, and will refuse to index an array outside of its permitted range - although there may be alternative access functions which bypass the checks. Other languages, such as C++, offer facilities to create a data type that functions like a standard array with bounds checkingBounds checking is the name given to any method of detecting whether or not the index given lies within the limits of the array. For example, accessing index 25 on an array of size 10 would be caught by bounds checking as an invalid index, because it does, or offer such a data structure in their standard library. The advantage of providing both checked and unchecked versions, whichever way round the problem is approached, is that you can choose the unchecked version in the rare applications where bounds checkingBounds checking is the name given to any method of detecting whether or not the index given lies within the limits of the array. For example, accessing index 25 on an array of size 10 would be caught by bounds checking as an invalid index, because it does would impose an unreasonable performance penalty, without sacrificing safety in cases where performance is less critical.
