Editing Array (data structure) (section)

==Efficiency==
Both ''store'' and ''select'' take (deterministic worst case) [[constant time]]. Arrays take linear ([[Big-O notation|O]](''n'')) space in the number of elements ''n'' that they hold.

In an array with element size ''k'' and on a machine with a cache line size of B bytes, iterating through an array of ''n'' elements requires the minimum of ceiling(''nk''/B) cache misses, because its elements occupy contiguous memory locations. This is roughly a factor of B/''k'' better than the number of cache misses needed to access ''n'' elements at random memory locations. As a consequence, sequential iteration over an array is noticeably faster in practice than iteration over many other data structures, a property called [[locality of reference]] (this does ''not'' mean however, that using a [[Perfect hash function|perfect hash]] or [[hash function#Trivial hash function|trivial hash]] within the same (local) array, will not be even faster - and achievable in [[constant time]]). Libraries provide low-level optimized facilities for copying ranges of memory (such as [[String.h|memcpy]]) which can be used to move [[Contiguous data storage|contiguous]] blocks of array elements significantly faster than can be achieved through individual element access. The speedup of such optimized routines varies by array element size, architecture, and implementation.

Memory-wise, arrays are compact data structures with no per-element [[Computational overhead|overhead]]. There may be a per-array overhead (e.g., to store index bounds) but this is language-dependent. It can also happen that elements stored in an array require ''less'' memory than the same elements stored in individual variables, because several array elements can be stored in a single [[Word (data type)|word]]; such arrays are often called ''packed'' arrays. An extreme (but commonly used) case is the [[bit array]], where every bit represents a single element. A single [[octet (computing)|octet]] can thus hold up to 256 different combinations of up to 8 different conditions, in the most compact form.

Array accesses with statically predictable access patterns are a major source of [[data parallelism]].

===Comparison with other data structures===
{{List data structure comparison}}
[[Dynamic array]]s or growable arrays are similar to arrays but add the ability to insert and delete elements; adding and deleting at the end is particularly efficient. However, they reserve linear ([[Big-O notation#Family of Bachmann–Landau notations|Θ]](''n'')) additional storage, whereas arrays do not reserve additional storage.

[[Associative array]]s provide a mechanism for array-like functionality without huge storage overheads when the index values are sparse. For example, an array that contains values only at indexes 1 and 2 billion may benefit from using such a structure. Specialized associative arrays with integer keys include [[Radix tree|Patricia trie]]s, [[Judy array]]s, and [[van Emde Boas tree]]s.

[[Self-balancing binary search tree|Balanced trees]] require O(log ''n'') time for indexed access, but also permit inserting or deleting elements in O(log ''n'') time,<ref>{{cite web|url=http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html|title=Counted B-Trees}}</ref> whereas growable arrays require linear (Θ(''n'')) time to insert or delete elements at an arbitrary position.

[[Linked list]]s allow constant time removal and insertion in the middle but take linear time for indexed access. Their memory use is typically worse than arrays, but is still linear.

[[Image:Array of array storage.svg|120px|left|A two-dimensional array stored as a one-dimensional array of one-dimensional arrays (rows).]]
An [[Iliffe vector]] is an alternative to a multidimensional array structure. It uses a one-dimensional array of [[reference (computer science)|references]] to arrays of one dimension less. For two dimensions, in particular, this alternative structure would be a vector of pointers to vectors, one for each row(pointer on c or c++). Thus an element in row ''i'' and column ''j'' of an array ''A'' would be accessed by double indexing (''A''[''i''][''j''] in typical notation). This alternative structure allows [[jagged array]]s, where each row may have a different size—or, in general, where the valid range of each index depends on the values of all preceding indices. It also saves one multiplication (by the column address increment) replacing it by a bit shift (to index the vector of row pointers) and one extra memory access (fetching the row address), which may be worthwhile in some architectures.