Editing Array (data structure) (section)

===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.