Array (data structure): Difference between revisions

Revision as of 16:39, 5 May 2024

Latest revision as of 17:47, 8 August 2025

(16 intermediate revisions by 10 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 19:

The term is also used, especially in the description of [[algorithm]]s, 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.

==History of java==

The first digital computers used machine-language programming to set up and access array structures for data tables, vector and matrix computations, and for many other purposes. [[John von Neumann]] wrote the first array-sorting program ([[merge sort]]) in 1945, during the building of the [[EDVAC|first stored-program computer]].<ref>{{TAOCP|volume=3|page=159}}</ref> Array indexing was originally done by [[self-modifying code]], and later using [[index register]]s and [[Addressing mode|indirect addressing]]. Some mainframes designed in the 1960s, such as the [[Burroughs large systems|Burroughs B5000]] and its successors, used [[memory segmentation]] to perform index-bounds checking in hardware.<ref>{{citation|title=Capability-based Computer Systems|first=Henry M.|last=Levy|publisher=Digital Press|year=1984|isbn=9780932376220|page=22}}.</ref>

Assembly languages generally have no special support for arrays, other than what the machine itself provides. The earliest high-level programming languages, including [[Fortran|FORTRAN]] (1957), [[Lisp (programming language)|Lisp]] (1958), [[COBOL]] (1960), and [[ALGOL|ALGOL 60]] (1960), had support for multi-dimensional arrays, and so has [[C (programming language)|C]] (1972). In [[C++]] (1983), class templates exist for multi-dimensional arrays whose dimension is fixed at runtime<ref name="garcia" /><ref name="veldhuizen" /> as well as for runtime-flexible arrays.<ref name="andres" />

==Applications of array==

Arrays are used to implement mathematical [[coordinate vector|vectors]] and [[matrix (mathematics)|matrices]], as well as other kinds of rectangular tables. Many [[database]]s, small and large, consist of (or include) one-dimensional arrays whose elements are [[record (computer science)|record]]s.

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.

Line 69 ⟶ 70:

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}}