(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.
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 or a linked list. Knuth use a balanced tree with a RANK field which supports Θ(log n) access by index and Θ(log n) insert and delete. [Knuth98, 3:471, Sect. 6.2.3]
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 Thu Nov 3 10:23:50 2005.
HTML page formatted Thu Nov 3 10:36:10 2005.
Cite this as:
Paul E. Black, "array", from
Dictionary of Algorithms and Data
Structures, Paul E. Black, ed.,
NIST.
http://www.nist.gov/dads/HTML/array.html
