In computer science an array is a data structure consisting of a group of elements that are accessed by indexing. A data structure in Computer science is a way of storing Data in a computer so that it can be used efficiently In Computer science theory a deque (short for double-ended queue &mdash Deque is usually pronounced deck In Computer science, a linked list is one of the fundamental Data structures and can be used to implement other data structures A queue (pronounced /kjuː/ is a particular kind of collection in which the entities in the collection are kept in order and the principal (or only operations on the collection In Computer science, a stack is an Abstract data type and Data structure based on the principle of Last In First Out (LIFO Computer science (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their A data structure in Computer science is a way of storing Data in a computer so that it can be used efficiently In Mathematics, the elements or members of a set (or more generally a class) are all those objects which when collected together make up the This is referring to Index in the context of Information Technology In most programming languages each element has the same data type and the array occupies a contiguous area of storage. A programming language is an Artificial language that can be used to write programs which control the behavior of a machine particularly a Computer. A data type in Programming languages is an attribute of a datum which tells the computer (and the programmer something about the kind of datum it is Most programming languages have a built-in array data type.

Some older languages referred to arrays as tables. This was the practice in COBOL. COBOL (ˈkoʊbɒl is one of the oldest programming languages still in active use ^[1]

Some programming languages support array programming (e. In Computer science, array programming languages (also known as vector or multidimensional languages generalize operations on scalars to apply g. , APL, newer versions of Fortran) which generalises operations and functions to work transparently over arrays as they do with scalars, instead of requiring looping over array members. Fortran (previously FORTRAN) is a general-purpose, procedural, imperative Programming language that is especially suited to

Multi-dimensional arrays are accessed using more than one index: one for each dimension.

Arrays can be classified as fixed-sized arrays (sometimes known as static arrays) whose size cannot change once their storage has been allocated, or dynamic arrays, which can be resized. In Computer science, a dynamic array, growable array, resizable array, dynamic table, or array list is an Array

Arrays

Variables normally only store a single value but, in some situations, it is useful to have a variable that can store a series of related values - using an array. For example, suppose a program is required that will calculate the average age among a group of six students. The ages of the students could be stored in six integer variables in C programming language:

int age1;
int age2;
int age3;
. . . 

However, a better solution would be to declare a six-element array:

int age[6];

This creates a six element array; the elements can be accessed as age[0] through age[5] in C.

(Note: in Visual Basic .NET the similar declaration Dim age(6) as Integer will create a seven element array, accessed as age(0) through age(6). Visual Basic.NET ( VBNET) is an object-oriented Computer language that can be viewed as an evolution of Microsoft's Visual Basic )

Implicit array

A new array object is implicitly created when an array initializer expression is evaluated; this can occur when a class or interface is initialized, when a new instance of a class is created, or when a local variable declaration statement is executed.

Applications

Because of their performance characteristics, arrays are used to implement other data structures, such as heaps, hash tables, deques, queues, stacks, strings, and VLists. In Computer science, a heap is a specialized tree -based Data structure that satisfies the heap property if B is a In Computer science, a hash table, or a hash map, is a Data structure that associates keys with values. In Computer science theory a deque (short for double-ended queue &mdash Deque is usually pronounced deck A queue (pronounced /kjuː/ is a particular kind of collection in which the entities in the collection are kept in order and the principal (or only operations on the collection In Computer science, a stack is an Abstract data type and Data structure based on the principle of Last In First Out (LIFO In Computer programming and some branches of Mathematics, a string is an ordered Sequence of Symbols. In Computer science, the VList is a persistent Data structure designed by Phil Bagwell in 2002 that combines the fast indexing of Arrays with

Some algorithms store a variable number of elements in part of a fixed-size array, which is equivalent to using dynamic array with a fixed capacity. In Computer science, a dynamic array, growable array, resizable array, dynamic table, or array list is an Array See dynamic array for details. In Computer science, a dynamic array, growable array, resizable array, dynamic table, or array list is an Array

Associative arrays provide a mechanism for array-like functionality without huge storage overheads when the index values are sparse. An associative array (also associative container, map, mapping, hash, dictionary, finite map, and in query-processing an Specialized associative arrays with integer keys include Patricia tries and Judy arrays. A radix tree, Patricia trie / tree, or crit bit tree is a specialized Set data structure based on the Trie that is used to store a set In Computer science and Software engineering, a Judy array is a complex but very fast Associative array Data structure for storing and looking

Indexing

Main article: Index (information technology)

The valid index values of each dimension of an array are a bounded set of integers. This is referring to Index in the context of Information Technology Programming environments that check indexes for validity are said to perform bounds checking. In Computer programming, bounds checking is any method of detecting whether a variable is within some bounds before its use

Index of the first element

The index of the first element (sometimes called the "origin") varies by language. There are three main implementations: zero-based, one-based, and n-based arrays, for which the first element has an index of zero, one, or a programmer-specified value. The zero-based array is more natural in the root machine language and was popularized by the C programming language, in which the abstraction of array is very weak, and an index n of a one-dimensional array is simply the offset of the element accessed from the address of the first (or "zero^th") element (scaled by the size of the element). Machine code or machine language is a system of instructions and data executed directly by a Computer 's Central processing unit. tags please moot on the talk page first! --> In Computing, C is a general-purpose cross-platform block structured One-based arrays are based on traditional mathematics notation for matrices and most, but not all, mathematical sequences. In Mathematics, a sequence is an ordered list of objects (or events n-based is made available so the programmer is free to choose the lower bound, which may even be negative, which is most naturally suited for the problem at hand.

The Comparison of programming languages (array), indicates the base index used by various languages. Syntax Array dimensions The following list contains Syntax examples on how to determine the dimensions (index of the first element the last element and or the

Supporters of zero-based indexing sometimes criticize one-based and n-based arrays for being slower. Often this criticism is mistaken when one-based or n-based array accesses are optimized with common subexpression elimination (for single dimensioned arrays) and/or with well-defined dope vectors (for multi-dimensioned arrays). In Computer science, common subexpression elimination (CSE is a Compiler optimization that searches for instances of identical expressions (ie they all In Computer programming, a dope vector is a Data structure used to hold information about an Array, especially its memory layout. However, in multidimensional arrays where the net offset into linear memory is computed from all of the indices, zero-based indexing is more natural, simpler, and faster. Edsger W. Dijkstra expressed an opinion in this debate: Why numbering should start at zero. Edsger Wybe Dijkstra ( May 11, 1930 &ndash August 6, 2002; ˈɛtsxər ˈwibə ˈdɛɪkstra was a Dutch computer scientist

The 0-based/1-based debate is not limited to just programming languages. For example, the ground-floor of a building is elevator button "0" in France, but elevator button "1" in the USA.

Indexing Methods

When the Array is implemented as continuous storage, the index-based access, e. g. to element n, is simply done (for zero-based indexing) by using the address of the first element and adding n · sizeof(one element). So this is a Θ(1) operation.

But there are cases, where continuous storage might be a bad idea:

• Insertion and deletion should also be a common operation, but continuous storage requires Θ(n) time for them. Here a balanced tree can be used, giving Θ(log n) for both index access and inserting/deleting. ^[2][3] For example the TextBuffer of GTK+ is implemented on top of a B-Tree, which has lower overhead compared to a binary tree like the AVL Tree. GTK+, or The GIMP Toolkit, is a Cross-platform Widget toolkit for creating Graphical user interfaces It is one of the most popular toolkits In Computer science, a B-tree is a Tree data structure that keeps data sorted and allows searches insertions and deletions in logarithmic amortized In Computer science, an AVL tree is a Self-balancing binary search tree, and it is the first such Data structure to be invented
• Allowing non-integer indices, which is also called an Associative array. An associative array (also associative container, map, mapping, hash, dictionary, finite map, and in query-processing an PHP Arrays are indexed by integers, but can also be accessed by string keys. PHP is a computer Scripting language. Originally designed for producing Dynamic web pages it has evolved to include a Command line interface capability

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 the multi-dimensional array 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 Mathematics, a matrix (plural matrices) is a rectangular table of elements (or entries) which may be Numbers or more generally 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:

It is most common to index this array using the RC-convention, where elements are referred in row, column fashion or , such as:

Common ways to index into multi-dimensional arrays include:

• Row-major order. In computing row-major order and column-major order describe methods for storing multidimensional arrays in linear memory Used most notably by statically-declared arrays in C. tags please moot on the talk page first! --> In Computing, C is a general-purpose cross-platform block structured The elements of each row are stored in order.

• Column-major order. In computing row-major order and column-major order describe methods for storing multidimensional arrays in linear memory Used most notably in Fortran. Fortran (previously FORTRAN) is a general-purpose, procedural, imperative Programming language that is especially suited to The elements of each column are stored in order.

• Arrays of arrays. Multi-dimensional arrays are typically represented by one-dimensional arrays of references (Iliffe vectors) to other one-dimensional arrays. In Computer science, a reference is an object containing information which refers to data stored elsewhere as opposed to containing the data itself In Computer programming, an Iliffe vector is a Data structure used to implement multi-dimensional Arrays Named after John K The subarrays can be either the rows or columns.

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 in predictable ways. In Mathematics, a matrix (plural matrices) is a rectangular table of elements (or entries) which may be Numbers or more generally 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. In Linear algebra, the main diagonal (sometimes leading diagonal or primary diagonal) of a matrix A is the collection of cells A_{ij}

References

1. ^ Using Tables in COBOL
2. ^ NIST's Dictionary of Algorithms and Data Structures: Array
3. ^ Counted B-Tree

See also

• Array slicing
• Collection class
• Comparison of programming languages (array)
• Parallel array
• Set (computer science)
• Sparse array
• Variable-length array
• wikibooks:Data Structures/Arrays
• wikibooks:Ada Programming/Types/array

External links

• NIST's Dictionary of Algorithms and Data Structures: Array