NIST

array

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

  1. new() returns an array
  2. get(i, set(i, v, A)) = v
  3. get(i, set(j, v, A)) = get(i, A) if i ≠ j
Compare this with a dictionary using integers as keys.

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

  1. get(i, new()) = vi

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.

  1. new(s) returns an array, which has a size s
  2. size(new(s)) = s
  3. size(set(i, v, A)) = size(A)
  4. get(i, set(i, v, A)) = v if 0 ≤ i < size(A)
  5. get(i, set(j, v, A)) = get(i, A) if i ≠ j
One-based or other indexing may be defined similarly.

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

Implementation

Sedgewick & Wayne's introduction and tutorial to arrays (Java). John Morris' Data Structures - Arrays(C). Bro. David Carlson's search, access, complexity, etc. tutorial and code (C++). Hudak, Peterson, and Fasel's section on arrays (Haskell). Read and write different arrays (Fortran, C++).
Go to the Dictionary of Algorithms and Data Structures home page.

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

Entry modified 23 May 2011.
HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:
Paul E. Black, "array", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 23 May 2011. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/array.html