(data structure)
Definition: A set of items which are randomly accessible by numeric index.
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
Jennifer E. Elaan's fast array algorithm, equivalent to Knuth's.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 2 November 2007.
HTML page formatted Fri Nov 2 17:19:29 2007.
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. 2 November 2007. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/array.html
