History and Applications of Arrays
– First array-sorting program (merge sort) written by John von Neumann in 1945
– Early array indexing done by self-modifying code
– Some mainframes in the 1960s used memory segmentation for index-bounds checking
– High-level programming languages like FORTRAN, Lisp, COBOL, and ALGOL 60 had support for multi-dimensional arrays
– C++ introduced class templates for fixed and runtime-flexible multi-dimensional arrays
– Arrays used for mathematical vectors, matrices, and rectangular tables
– Many databases consist of one-dimensional arrays with record elements
– Arrays used to implement other data structures like lists, heaps, hash tables, queues, stacks, and strings
– Arrays used for in-program dynamic memory allocation
– Arrays used as control tables to determine program control flow
Element Identifier and Addressing Formulas
– Indexes (subscripts) used to select individual objects in an array
– Three ways to index elements: zero-based indexing, one-based indexing, and n-based indexing
– Zero-based indexing is a design choice in influential programming languages like C, Java, and Lisp
– Arrays can have multiple dimensions, requiring multiple indices for access
– The number of indices needed to specify an element is called the dimensionality or rank of the array
One-dimensional Arrays
– One-dimensional arrays are linear arrays with a single subscript for element access
– Subscript can represent a row or column index
– Accessing elements in a one-dimensional array is straightforward
– One-dimensional arrays are commonly used in various applications
– Can be implemented efficiently with little space overhead
Array Data Type
– Array data type provided by high-level programming languages
– Collection of values or variables selected by one or more run-time indices
– Array types often implemented by array structures, hash tables, linked lists, search trees, etc.
– Array data type can be implemented using various data structures
– Array data type is an abstract data type capturing essential properties of arrays
Multidimensional Arrays and Efficiency
– Addressing formula for element with indices: [row][column]
– Formula: base address + (row * row address increment) + (column * column address increment)
– Example: int a[2][3]
– Array has 2 rows and 3 columns
– Elements stored linearly, starting from first row to second row
– Static arrays have a fixed size and do not allow insertion or removal of elements
– Dynamic arrays can be implemented by allocating a new array and copying contents
– Insertions at the end of the array require amortized constant time
– Store and select operations on arrays take constant time
– Arrays take linear space in the number of elements they hold
– Sequential iteration over an array is faster due to locality of reference
– Arrays have no per-element overhead and are memory-wise compact
– Optimized routines like memcpy can significantly speed up copying array elements
This article needs additional citations for verification. (September 2008) |
In computer science, an array is a data structure consisting of a collection of elements (values or variables), of same memory size, each identified by at least one array index or key. An array is stored such that the position of each element can be computed from its index tuple by a mathematical formula. The simplest type of data structure is a linear array, also called one-dimensional array.
For example, an array of ten 32-bit (4-byte) integer variables, with indices 0 through 9, may be stored as ten words at memory addresses 2000, 2004, 2008, ..., 2036, (in hexadecimal: 0x7D0, 0x7D4, 0x7D8, ..., 0x7F4) so that the element with index i has the address 2000 + (i × 4).
The memory address of the first element of an array is called first address, foundation address, or base address.
Because the mathematical concept of a matrix can be represented as a two-dimensional grid, two-dimensional arrays are also sometimes called "matrices". In some cases the term "vector" is used in computing to refer to an array, although tuples rather than vectors are the more mathematically correct equivalent. Tables are often implemented in the form of arrays, especially lookup tables; the word "table" is sometimes used as a synonym of array.
Arrays are among the oldest and most important data structures, and are used by almost every program. They are also used to implement many other data structures, such as lists and strings. They effectively exploit the addressing logic of computers. In most modern computers and many external storage devices, the memory is a one-dimensional array of words, whose indices are their addresses. Processors, especially vector processors, are often optimized for array operations.
Arrays are useful mostly because the element indices can be computed at run time. Among other things, this feature allows a single iterative statement to process arbitrarily many elements of an array. For that reason, the elements of an array data structure are required to have the same size and should use the same data representation. The set of valid index tuples and the addresses of the elements (and hence the element addressing formula) are usually, but not always, fixed while the array is in use.
The term "array" may also refer to an array data type, a kind of data type provided by most high-level programming languages that consists of a collection of values or variables that can be selected by one or more indices computed at run-time. Array types are often implemented by array structures; however, in some languages they may be implemented by hash tables, linked lists, search trees, or other data structures.
The term is also used, especially in the description of algorithms, to mean associative array or "abstract array", a theoretical computer science model (an abstract data type or ADT) intended to capture the essential properties of arrays.
