(data structure)

**Definition:**
An assemblage of items that are randomly accessible by integers, the index.

**Formal Definition:** Ignoring size an array may be seen as an *abstract data type* with the operations new(), set(i, v, A), and get(i, A), where i is a numeric index, v is a value, and A is an array. The operations may be defined with *axiomatic semantics* as follows.

- new() returns an array
- get(i, set(i, v, A)) = v
- get(i, set(j, v, A)) = get(i, A) if i ≠ j

If the contents of a new array are set to some implicit initial value v_{i}, we could add the following rule for get.

- get(i, new()) = v
_{i}

Typically arrays have a fixed size and use either *0-based indexing* or *one-based indexing*. Fixed initial size and 0-based indexing may incorporated as follows.

- new(s) returns an array, which has a size s
- size(new(s)) = s
- size(set(i, v, A)) = size(A)
- get(i, set(i, v, A)) = v if 0 ≤ i < size(A)
- get(i, set(j, v, A)) = get(i, A) if i ≠ j

**Specialization** (... is a kind of me.)

*dynamic array*, *sorted array*.

**Aggregate child** (... is a part of or used in me.)

*array index*, *one-based indexing*, *0-based indexing*.

**See also**
*associative array*, *matrix*, *huge sparse array*.

*Note:
An unordered array must be searched with a linear search. Average search time may be improved using a move-to-front heuristic in some cases. An external index, such as a hash table or inverted index may help make an array search quicker and speed overall processing if the array is not changed often. If the array is kept sorted, a binary search or interpolation search is faster. *

Inserting into an array takes *Θ*(n) time. If that's too slow, use a *balanced tree*, *skip list*, or a *linked list*. Knuth uses a balanced tree with a RANK field that supports *Θ*(log n) access by index and *Θ*(log n) insert and delete. [Knuth98, 3:471, Sect. 6.2.3]

* If it takes too long to initialize a big array of size S, a huge sparse array takes time proportional to the number of accesses and only Θ(S) extra space.*

Author: PEB

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified 23 May 2011.

HTML page formatted Tue Dec 6 16:16:32 2011.

Cite this as:

Paul E. Black, "array", in
*Dictionary of Algorithms and Data
Structures* [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 23 May 2011. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/array.html