Array data structure

arrayarraysvectorarray indexindicesone-dimensional arrayvectorsarray elementindexmatrix
In computer science, an array data structure, or simply an array, is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key.wikipedia
415 Related Articles

Lookup table

lookuplook-up tabletable lookup
Tables are often implemented in the form of arrays, especially lookup tables; the word table is sometimes used as a synonym of array.
In computer science, a lookup table is an array that replaces runtime computation with a simpler array indexing operation.

Data structure

data structuresstructurestructures
In computer science, an array data structure, or simply an array, is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key.
Thus, the array and record data structures are based on computing the addresses of data items with arithmetic operations, while the linked data structures are based on storing addresses of data items within the structure itself.

Vector processor

vector processingvectorarray processor
Processors, especially vector processors, are often optimized for array operations.
In computing, a vector processor or array processor is a central processing unit (CPU) that implements an instruction set containing instructions that operate on one-dimensional arrays of data called vectors, compared to the scalar processors, whose instructions operate on single data items.

Linked list

singly linked listlinked listsdynamic list
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.
Arrays have better cache locality compared to linked lists.

Associative array

mapdictionariesdictionary
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.
In some cases it is also possible to solve the problem using directly addressed arrays, binary search trees, or other more specialized structures.

List (abstract data type)

listlistsList (computing)
They are also used to implement many other data structures, such as lists and strings.
Some languages may allow list types to be indexed or sliced like array types, in which case the data type is more accurately described as an array.

Array data type

arrayarraysmulti-dimensional array
The term array is often used to mean 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 data structures, but sometimes by other means, such as hash tables, linked lists, or search trees.

Index register

index registersIndexindex (B) registers
p. 159 Array indexing was originally done by self-modifying code, and later using index registers and indirect addressing.
An index register in a computer's CPU is a processor register used for modifying operand addresses during the run of a program, typically for doing vector/array operations.

Central processing unit

CPUprocessorprocessors
Processors, especially vector processors, are often optimized for array operations.
While performing various operations, CPUs need to calculate memory addresses required for fetching data from the memory; for example, in-memory positions of array elements must be calculated before the CPU can fetch the data from actual memory locations.

Table (information)

tabletabulartables
Tables are often implemented in the form of arrays, especially lookup tables; the word table is sometimes used as a synonym of array.
At a programming level, software may be implemented using constructs generally represented or understood as tabular, whether to store data (perhaps to memoize earlier results), for example, in arrays or hash tables, or control tables determining the flow of program execution in response to various events or inputs.

Sorted array

Array-based implementations of other data structures are frequently simple and space-efficient (implicit data structures), requiring little space overhead, but may have poor space complexity, particularly when modified, compared to tree-based data structures (compare a sorted array to a search tree).
A sorted array is an array data structure in which each element is sorted in numerical, alphabetical, or some other order, and placed at equally spaced addresses in computer memory.

Control table

quotations
They are known in this context as control tables and are used in conjunction with a purpose built interpreter whose control flow is altered according to values contained in the array.
Control tables are tables that control the control flow or play a major part in program control.

Stack (abstract data type)

stackLIFOstacks
Arrays are used to implement other data structures, such as lists, heaps, hash tables, deques, queues, stacks, strings, and VLists.
A stack can be easily implemented either through an array or a linked list.

Variable (computer science)

variablevariablesscalar
In computer science, an array data structure, or simply an array, is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key.
Single-character names are most commonly used only for auxiliary variables; for instance,, for array index variables.

Runtime (program lifecycle phase)

run timerun-timeruntime
Arrays are useful mostly because the element indices can be computed at run time.
Logic errors and array bounds checking are examples.

Algorithm

algorithmsalgorithm designcomputer algorithm
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.

Implicit data structure

implicit
Array-based implementations of other data structures are frequently simple and space-efficient (implicit data structures), requiring little space overhead, but may have poor space complexity, particularly when modified, compared to tree-based data structures (compare a sorted array to a search tree).
A trivial example of an implicit data structure is an array data structure, which is an implicit data structure for a list, and requires only the constant overhead of the length; unlike a linked list, which has a pointer associated with each data element, which explicitly gives the relationship from one element to the next.

Addressing mode

indirect addressingconditional executionindirect address
p. 159 Array indexing was originally done by self-modifying code, and later using index registers and indirect addressing.
The base register could contain the start address of an array or vector data structure, and the index could contain the offset of the one particular array element required.

Zero-based numbering

zero-basedzero-based indexing0-based
For this reason, the C programming language specifies that array indices always begin at 0; and many programmers will call that element "zeroth" rather than "first".
In computer science, array indices usually start at 0 in modern programming languages, so computer programmers might use zeroth in situations where others might use first, and so forth.

Pointer (computer programming)

pointerpointerspointer arithmetic
The array may contain subroutine pointers (or relative subroutine numbers that can be acted upon by SWITCH statements) that direct the path of the execution.
When an aggregate is entirely composed of the same type of primitive, the aggregate may be called an array; in a sense, a multi-byte word primitive is an array of bytes, and some programs use words in this way.

String (computer science)

stringstringscharacter string
They are also used to implement many other data structures, such as lists and strings. Arrays are used to implement other data structures, such as lists, heaps, hash tables, deques, queues, stacks, strings, and VLists.
A string is generally considered as a data type and is often implemented as an array data structure of bytes (or words) that stores a sequence of elements, typically characters, using some character encoding.

Database

database management systemdatabasesDBMS
Many databases, small and large, consist of (or include) one-dimensional arrays whose elements are records.

Abstract data type

abstract data typesabstract data structureabstract
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.
Thus, for example, an abstract stack can be implemented by a linked list or by an array.

Locality of reference

localitydata localitycache locality
As a consequence, sequential iteration over an array is noticeably faster in practice than iteration over many other data structures, a property called locality of reference (this does not mean however, that using a perfect hash or trivial hash within the same (local) array, will not be even faster - and achievable in constant time).
Sequential locality, a special case of spatial locality, occurs when data elements are arranged and accessed linearly, such as, traversing the elements in a one-dimensional array.

Time complexity

polynomial timelinear timeexponential time
As a consequence, sequential iteration over an array is noticeably faster in practice than iteration over many other data structures, a property called locality of reference (this does not mean however, that using a perfect hash or trivial hash within the same (local) array, will not be even faster - and achievable in constant time). Both store and select take (deterministic worst case) constant time.
For example, accessing any single element in an array takes constant time as only one operation has to be performed to locate it.