Array (data structure)

Lore & Background

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. Array indexing was originally done by self-modifying code, and later using index registers and indirect addressing. Some mainframes designed in the 1960s, such as the Burroughs B5000 and its successors, used memory segmentation to perform index-bounds checking in hardware. Assembly languages generally have no special support for arrays, other than what the machine itself provides. In C++, class templates for multi-dimensional arrays with runtime-fixed dimensions are not part of the standard library; std::array has compile-time fixed size, and std::vector is runtime-flexible but not a multi-dimensional array template. Arrays are used to implement mathematical vectors and matrices, as well as other kinds of rectangular tables. Many databases consist of or include one-dimensional arrays whose elements are records. Arrays are also used to implement other data structures such as lists, heaps, hash tables, deques, queues, stacks, strings, and VLists. One or more large arrays are sometimes used to emulate in-program dynamic memory allocation, particularly memory pool allocation.

Reader's Guide

Arrays are fundamental to computing because they effectively exploit the addressing logic of computers. In most modern computers and many external storage devices, memory itself is a one-dimensional array of words, whose indices are their addresses. Processors, especially vector processors, are often optimized for array operations. The ability to compute element indices at run time allows a single iterative statement to process arbitrarily many elements, which is why array elements are required to have the same size and data representation. The term 'array' also refers to an array data type provided by most high-level programming languages, consisting of a collection of values or variables selectable by one or more indices computed at run time. Array types are often implemented by array structures, though in some languages they may be implemented by hash tables, linked lists, search trees, or other data structures. The term is also used to mean associative array or 'abstract array', a theoretical computer science model intended to capture the essential properties of arrays. Arrays can be used to determine partial or complete control flow in programs as a compact alternative to multiple IF statements, in which context they are known as control tables. They 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 pointers or relative subroutine numbers that direct the path of execution.

Did You Know?

• Array indexing was originally done by self-modifying code, and later using index registers and indirect addressing.
• The Burroughs B5000 and its successors used memory segmentation to perform index-bounds checking in hardware.
• In C++, the standard library does not include class templates for multi-dimensional arrays with runtime-fixed dimensions; std::array has compile-time fixed size, and std::vector is runtime-flexible but not a multi-dimens

Contiguous Memory and the Addressing Formula

An array occupies a single, unbroken block of memory in which every element occupies the same number of bytes. Because the elements are uniform in size and representation, the hardware can locate any member of the collection through a simple arithmetic expression: multiply the index by the element size and add the result to what is variously called the first address, foundation address, or base address. A concrete illustration makes this clear. The simplest incarnation of this idea is the one-dimensional, or linear, array—a mutable, ordered sequence of same-typed values. More complex structures layer additional indices into what is known as an index tuple, but the underlying principle remains: a mathematical formula, fixed for the lifetime of the array, maps every valid index tuple to a unique memory location. This deterministic, run-time-computable addressing is precisely what makes arrays so natural to the addressing logic of modern processors and external storage devices, where memory itself is essentially a one-dimensional array of words indexed by their addresses.

From Machine Code to High-Level Languages

The earliest digital computers had no built-in array syntax; programmers wrote machine-language instructions directly to lay out data tables, perform vector and matrix calculations, and manage other tabular structures. In those early days, indexing was accomplished through self-modifying code, a technique later supplanted by dedicated index registers and indirect addressing modes. By the 1960s, mainframes such as the Burroughs B5000 and its successors went a step further, embedding index-bounds checking directly in hardware via memory segmentation. Assembly languages, however, still offered no special array constructs beyond what the machine itself provided.

The Workhorse Beneath Other Structures

Arrays serve as the foundational building block for a remarkable range of higher-level data structures. Lists, heaps, hash tables, deques, queues, stacks, strings, and VLists can all be implemented on top of arrays, and these array-based versions are often praised for their simplicity and minimal space overhead—what is sometimes called an implicit data structure. The trade-off is that certain modifications, such as inserting into a sorted array, can carry poor space complexity compared with tree-based alternatives like search trees. Beyond structural reuse, arrays appear in databases of every scale, where one-dimensional collections of records form the backbone of storage. In the realm of memory management, one or more large arrays have historically been used to emulate dynamic allocation, particularly memory-pool allocation, and in some eras this was the only portable way to obtain dynamic memory. Arrays also play a role in control flow: so-called control tables store subroutine pointers or relative subroutine numbers that a purpose-built interpreter reads to alter execution path, offering a compact alternative to long chains of conditional statements.

Indexing Conventions and the Abstract Array

The way an array's elements are numbered is not universal. Zero-based indexing, in which the first element carries subscript 0, is the convention adopted by influential languages such as C, Java, and Lisp, and it simplifies implementation because the subscript becomes a direct offset from the array's starting position. One-based indexing, where the first element is subscript 1, is equally common. A third, more flexible approach—n-based indexing—lets the programmer choose any base value, and languages that support it often also permit negative indices, enumeration types, or even characters as valid subscripts. Beyond concrete implementations, the word array carries additional meanings. In most high-level languages it names a data type whose values are selected by run-time-computed indices, though the underlying storage might actually be a hash table, linked list, or search tree. In theoretical computer science, the associative array or abstract array serves as an abstract data type capturing the essential properties of arrays independent of any particular implementation, and in computing the term vector is sometimes used loosely for an array even though tuples are the more mathematically precise equivalent.