Array (data structure): Difference between revisions

Revision as of 14:48, 25 March 2024

Latest revision as of 17:47, 8 August 2025

(19 intermediate revisions by 11 users not shown)

Line 4:

{{More citations needed|date=September 2008}}

In [[computer science]], an '''array''' is a [[data structure]] consisting of a collection of ''elements'' ([[value (computer science)|values]] or [[variable (programming)|variables]]), of same memory size, each identified by at least one ''array index'' or ''key'', a collection of which may be a [[tuple]], known as an index tuple. An array is stored such that the position (memory address) of each element can be computed from its index [[tuple]] by a mathematical formula.<ref>{{cite web|url=https://xlinux.nist.gov/dads/HTML/array.html|title=array|last=Black|first=Paul E.|date=13 November 2008|work=[[Dictionary of Algorithms and Data Structures]]|publisher=[[National Institute of Standards and Technology]]|access-date=22 August 2010}}</ref><ref name="andres">{{cite arXiv |eprint=1008.2909 |author1=Bjoern Andres |author2=Ullrich Koethe |author3=Thorben Kroeger |author4=Hamprecht |title=Runtime-Flexible Multi-dimensional Arrays and Views for C++98 and C++0x |class=cs.DS |year=2010}}</ref><ref name="garcia">{{Cite journal|last1=Garcia|first1=Ronald |first2=Andrew |last2=Lumsdaine|year=2005|title=MultiArray: a C++ library for generic programming with arrays|journal=Software: Practice and Experience|volume=35|issue=2|pages=159–188|issn=0038-0644|doi=10.1002/spe.630|s2cid=10890293 }}</ref> The simplest type of data structure is a linear array, also called a 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 [[Word (data type)|words]] at memory addresses 2000, 2004, 2008, ..., 2036, (in [[hexadecimal]]: <code>0x7D0</code>, <code>0x7D4</code>, <code>0x7D8</code>, ..., <code>0x7F4</code>) so that the element with index ''i'' has the address 2000 + (''i'' × 4).<ref>David R. Richardson (2002), The Book on Data Structures. iUniverse, 1121112 pages. {{ISBN|0-595-24039-9}}, {{ISBN|978-0-595-24039-5}}.</ref>

The memory address of the first element of an array is called first address, foundation address, or base address.

Line 31:

One or more large arrays are sometimes used to emulate in-program [[dynamic memory allocation]], particularly [[memory pool]] allocation. Historically, this has sometimes been the only way to allocate "dynamic memory" portably.

Arrays can be used to determine partial or complete [[control flow]] in programs, as a compact alternative to (otherwise repetitive) multiple <code>IF</code> statements. TheyIn arethis knowncontext, inthey thisare contextknown as [[control table]]s and are used in conjunction with a purpose -built interpreter whose [[control flow]] is altered according to values contained in the array. The array may contain [[subroutine]] [[Pointer (computer programming)|pointers]] (or relative subroutine numbers that can be acted upon by [[Switch statement|SWITCH]] statements) that direct the path of the execution of the program.

==Element identifier and addressing formulas==

Line 60:

===One-dimensional arrays===

[[File:1D array diagram.svg|thumb|Diagram of a typical 1D array]]

A one-dimensional array (or single dimension array) is a type of linear array. Accessing its elements involves a single subscript which can either represent a row or column index.

As an example consider the C declaration <code>int anArrayName[10];</code> which declares a one-dimensional array of ten integers. Here, the array can store ten elements of type <code>int</code> . This array has indices starting from zero through nine. For example, the expressions <code>anArrayName[0]</code> and <code>anArrayName[9]</code> are the first and last elements respectively.

Line 68 ⟶ 69:

If the valid element indices begin at 0, the constant ''B'' is simply the address of the first element of the array. For this reason, the [[C (programming language)|C programming language]] specifies that array indices always begin at 0; and many programmers will call that element "[[zero-based numbering|zeroth]]" rather than "first".

However, one can choose the index of the first element by an appropriate choice of the base address ''B''. For example, if the array has five elements, indexed 1 through 5, and the base address ''B'' is replaced by {{nowrap|''B'' + 30''c''}}, then the indices of those same elements will be 31 to 35. If the numbering does not start at 0, the constant ''B'' may not be the address of any element.

[[File:2D array diagram.svg|thumb|Diagram of a typical 2D array]]

===Multidimensional arrays===

[[File:3D array diagram.svg|thumb|Diagram of a typical 3D array]]

For a multidimensional array, the element with indices ''i'',''j'' would have address ''B'' + ''c'' · ''i'' + ''d'' · ''j'', where the coefficients ''c'' and ''d'' are the ''row'' and ''column address increments'', respectively.

Line 87 ⟶ 89:

===Dope vectors===

{{Main|Dope vector}}

The addressing formula is completely defined by the dimension ''d'', the base address ''B'', and the increments ''c''₁, ''c''₂, ..., ''c''_''k''. It is often useful to pack these parameters into a record called the array's ''descriptor'' or ''stride vector'' or ''[[dope vector]]''.<ref name="andres" /><ref name="garcia" /> The size of each element, and the minimum and maximum values allowed for each index may also be included in the dope vector. The dope vector is a complete [[handle (computing)|handle]] for the array, and is a convenient way to pass arrays as arguments to [[subroutine|procedures]]. Many useful [[array slicing]] operations (such as selecting a sub-array, swapping indices, or reversing the direction of the indices) can be performed very efficiently by manipulating the dope vector.<ref name="andres" />

The addressing formula is completely defined by the dimension ''d'', the base address ''B'', and the increments ''c''₁, ''c''₂, ..., ''c''_''k''. It is often useful to pack these parameters into a record called the array's ''descriptor'', or ''stride vector'', or ''[[dope vector]]''.<ref name="andres" /><ref name="garcia" /> The size of each element, and the minimum and maximum values allowed for each index may also be included in the dope vector. The dope vector is a complete [[handle (computing)|handle]] for the array, and is a convenient way to pass arrays as arguments to [[subroutine|procedures]]. Many useful [[array slicing]] operations (such as selecting a sub-array, swapping indices, or reversing the direction of the indices) can be performed very efficiently by manipulating the dope vector.<ref name="andres" />

===Compact layouts===

Line 176 ⟶ 180:

{{Commons category|Array data structure}}

{{Wiktionary|array}}

* {{Wikibooks- inline|Data Structures/Arrays}}

{{-Clear}}

{{Data structures}}

{{Parallel computing}}