Array

From Academic Kids

In computer programming, an array, also known as a vector or list, is one of the simplest data structures. Arrays hold equally-sized data elements, generally of the same data type. Individual elements are accessed by index using a consecutive range of integers, as opposed to an associative array. Some arrays are multi-dimensional, meaning they are indexed by a fixed number of integers, for example by a tuple of four integers. Generally, one- and two-dimensional arrays are the most common.

Most programming languages have arrays as a built-in data type. Some programming languages (such as APL, Fortran, and J) generalize the available operations and functions to work transparently over arrays as well as scalars, providing a higher-level manipulation than most other languages, which require loops over all the individual members of the arrays.

Contents

Advantages and disadvantages

Arrays permit efficient (constant time, O(1)) random access but not efficient insertion and deletion of elements (which are O(n), where n is the size of the array). Linked lists have the opposite trade-off. Consequently, arrays are most appropriate for storing a fixed amount of data which will be accessed in an unpredictable fashion, and linked lists are best for a list of data which will be accessed sequentially and updated often with insertions or deletions.

Another advantage of arrays that has become very important on modern architectures is that iterating through an array has good locality of reference, and so is much faster than iterating through (say) a linked list of the same size, which tends to jump around in memory. However, an array can also be accessed in a random way, as is done with large hash tables, and in this case this is not a benefit.

Arrays also are among the most compact data structures; storing 100 integers in an array takes only 100 times the space required to store an integer, plus perhaps a few bytes of overhead for the whole array. Any pointer-based data structure, on the other hand, must keep its pointers somewhere, and these occupy additional space. This extra space becomes more significant as the data elements become smaller. For example, an array of ASCII characters takes up one byte per character, while on a 32-bit platform, which has 4-byte pointers, a linked list requires at least five bytes per character. Conversely, for very large elements, the space difference becomes a negligible fraction of the total space.

Because arrays have a fixed size, there are some indexes which refer to invalid elements — for example, the index 17 in an array of size 5. What happens when a program attempts to refer to these varies from language to language and platform to platform. For more information, see bounds checking.

Uses

Although useful in their own right, arrays also form the basis for several more complex data structures, such as heaps, hash tables, and VLists, and can be used to represent strings, stacks and queues. They also play a more minor role in many other data structures. All of these applications benefit from the compactness and locality of arrays.

One of the disadvantages of an array is that it has a single fixed size, and although its size can be altered in many environments, this is an expensive operation. Growable arrays or dynamic arrays are arrays which automatically perform this resizing as late as possible, when the programmer attempts to add an element to the end of the array and there is no more space. To average the high cost of resizing over a long period of time (we say it is an amortized cost), they expand by a large amount, and when the programmer attempts to expand the array again, it just uses more of this reserved space.

In the C programming language, one-dimensional character arrays are used to store null-terminated strings, so called because the end of the string is indicated with a special reserved character called a null character ('\0') (see also C string).

Finally, in some applications where the data are the same or are missing for most values of the indexes, or for large ranges of indexes, space is saved by not storing an array at all, but having an associative array with integer keys. There are many specialized data structures specifically for this purpose, such as Patricia tries and Judy arrays. Example applications include address translation tables and routing tables.

Indices into arrays

Although abstractions for arrays in most programming languages are very similar, one strong point of contention has arisen: the index used to refer to the first element. There are three main solutions: zero-based, one-based, and n-based arrays, for which the first element has index zero, one, or a programmer-specified value, respectively.

This is mainly a stylistic concern. The zero-based array was made popular by the C programming language, in which the abstraction of array is very weak, and an index n of an array is simply the address of the first element offset by n units. Accordingly, index 0 points to the first element of the array. Descendants of C such as C++, Java, and C# inherit this behavior. One-based arrays, used for example in BASIC, are based on traditional mathematics notation and simple counting, which begins with one. Languages that allow the valid minimum and maximum indices to be specified by the programmer include Ada, Visual Basic (though not Visual Basic .NET,) Pascal, and PL/1, although most of these default to one-based if a minimum index is not specified.

The conflict over the "right" way to do array indexing has impacted programmer culture. When supporters of one-based arrays decried zero-based arrays as unnatural, saying for example that we start numbered lists from 1, supporters of zero-based arrays retaliated by starting their own lists from zero in their daily lives. This practice can still be observed, and is often done for humor.

Supporters of zero-based indexing often criticise one-based and n-based arrays for being slower. While this is true, a one-based or n-based array access can be easily optimized, for example either with a very simple Common subexpression elimination or the use of a well defined Dope vector - to name only two options available. So in real-life applications one-based and n-based arrays are just as fast as zero-based arrays.

Multi-dimensional arrays

Ordinary arrays are indexed by a single integer. Also useful, particularly in numerical and graphics applications, is the concept of a multi-dimensional array, in which we index into the array using an ordered list of integers, such as in a[3,1,5]. The number of integers in the list used to index into it is always the same and is referred to as the array's dimensionality, and the bounds on each of these are called the array's dimensions. An array with dimensionality k is often called k-dimensional. One-dimensional arrays correspond to the simple arrays discussed thus far; two-dimensional arrays are a particularly common representation for matrices. In practice, the dimensionality of an array rarely exceeds three.

Mapping a one-dimensional array into memory is obvious, since memory is logically itself a (very large) one-dimensional array. When we reach higher-dimensional arrays, however, the problem is no longer obvious. Suppose we want to represent this simple two-dimensional array:

<math>

\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} <math>

A few common representations include:

  • Row-major order. Used most notably by statically-declared arrays in C. The elements of each row are stored in order.
1 2 3 4 5 6 7 8 9
  • Column-major order. Used most notably in Fortran. The elements of each column are stored in order.
1 4 7 2 5 8 3 6 9
  • Arrays of arrays. Multi-dimensional arrays are represented by one-dimensional arrays of pointers to other one-dimensional arrays. The subarrays can be either the rows or columns.

 A two-dimensional array stored as a one-dimensional array of one-dimensional arrays.

The first two forms are more compact and have potentially better locality of reference, but are also more limiting; the arrays must be rectangular, meaning that no row can contain more elements than any other. Arrays of arrays, on the other hand, allow the creation of ragged arrays, also called jagged arrays, in which the valid range of one index depends on the value of another, or in this case, simply that different rows can be different sizes. Arrays of arrays are also of value in programming languages that only supply one-dimensional arrays as primitives.

In many applications, such as numerical applications working with matrices, we iterate over rectangular two-dimensional arrays, especially two-dimensional arrays, in interesting ways. For example, computing an element of the matrix product AB involves iterating over a row of A and a column of B simultaneously. In mapping the individual array indexes into memory, we wish to exploit locality of reference as much as we can. A compiler can sometimes automatically choose the layout for an array so that sequentially accessed elements are stored sequentially in memory; in our example, it might choose row-major order for A, and column-major order for B. Even more exotic orderings can be used, for example if we iterate over the main diagonal of a matrix.

See also

External link

es:Array fr:Tableau it:Array he:מערך (מבנה נתונים) nl:Array ja:配列 pl:Tablica sv:Array

Navigation

Academic Kids Menu

  • Art and Cultures
    • Art (http://www.academickids.com/encyclopedia/index.php/Art)
    • Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (http://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools