The Humble Array
The array is a collection of elements that are stored in memory with each element the same size such that the position of each element can be calculated from its index(es) and the memory address of the first element (also called the first address or foundation address). The array data structure is different from an array data type that exists in many programming languages, which are implemented by a variety of different data structures including arrays, hash tables, and linked lists. The array data structure also should not be confused with an associative array, an abstract data type that considers the behavior of data as seen by a user instead of being a concrete representation of how data is implemented.
The simplest array and simplest data structure is the linear or one-dimensional array, sometimes called a vector although there is a slight difference in that vectors can grow in size by doubling their allotted space. Arrays can also be two-dimensional arrays also called matrixes or multi-dimensional. Multi-dimensional are identified by one index per each dimension.
Arrays are important and space-efficient because of their simplicity; they don’t store much information beyond the inputted data. They are ubiquitous and many other data structures such as lists, heaps, hash tables, queues, stacks, and strings are implemented using arrays.
In terms of complexity accessing data is O(1) and other operations are O(n).
