Array
Array as a data structure, is simply a collection of elements each identified by an index or a key. In many cases you can consider an array as a synonym of the word table. One can use arrays to implement other data structures and concepts such as strings, lists and lookup tables. Some programming languages use hash tables, linked lists, search trees etc. to implement arrays.
From a mathematical perspective
A tuple is a finite ordered sequence of elements. A sequence of n (non-negative integer) elements is an n-tuple. 0-tuple is an empty sequence. In this sense, one could consider tuples as the mathematical equivalent of arrays.
Arrays exploit the addressing logic of computers. The memory address of the first element of an array is called the foundation address.
An array is stored so that the position of each element can be computed from its index tuple by a mathematical formula. For example, an array of 10 32-bit integer variables, with indices 0 through 9, may be stored as 10 words at memory addresses 2000, 2004, 2008, … 2036, so that the element with index i has the address 2000 + 4 × i.
A matrix can be represented as a two-dimensional grid, hence two-dimensional arrays can be considered as matrices.
Arrays in different programming languages
C Arrays
Arrays in C store related data under a single variable name with an index, also known as the subscript. It’s simply a list of ordered grouping for variables of the same type. Arrays can be considered as a constant pointer.
You declare an array as type name[number of elements]={comma-separated values} e.g.
int point[6]={0,0,1,0,0,0}; or char letters[29]; or float matrix[ NROWS ][ NCOLS ];
You can omit the array dimension if you type it as int point[]={0,0,1,0,0,0}; (The index in C is actually an offset from the beginning of the array. The first element of this array is point[0])
If the dimension is specified, but not all elements in the array are initialized, the remaining elements will contain a value of 0.
int numbers[2000]={245}; sets the first value of the array to 245, and the rest to 0.
char two_dim[3][5]; is a two dimensional array that has 3 rows and 5 columns.
To access a value we need two indexes:
char ch;
ch = two_dim[2][4];
two_dim[0][0] = 'x';
/* Initialization of a multi-dimensional array */
int two_d[2][3] = { { 5, 2, 1 }, { 6, 7, 8 } };
/* More examples */
int i = 5, intArray[ 6 ] = { 1, 2, 3, 4, 5, 6 }, k;
float sum = 0.0f, floatArray[ 100 ] = { 1.0f, 5.0f, 20.0f };
double piFractions[ ] = { 3.141592654, 1.570796327, 0.785398163 };
/* In C99 there is an alternative mechanism that allows you to initialize arrays that have non-sequential indexes.
* This method can be mixed in with traditional initialization.
*
* If the size of the array is not given,
* the largest initialized position determines the size of the array.
*/
int numbers[ 100 ] = { 1, 2, 3, [10] = 10, 11, 12, [60] = 50, [42] = 420 }; #include <stdlib.h>
#include <stdio.h>
int main( void ) {
int i, fibonacci[ 20 ]; /* first 20 Fibonacci numbers */
fibonacci[ 0 ] = 0;
fibonacci[ 1 ] = 1;
for( i = 2; i < 20; i++ )
fibonacci[ i ] = fibonacci[ i - 2 ] + fibonacci[ i - 1 ];
for( i = 0; i < 20; i++ )
printf( "Fibonacci[ %d ] = %f\n", i, fibonacci[ i ] );
}Array keys have to be integers and need to be continuous. If you have the keys 0, 1 and 2, then the next key has to be 3 and can’t be 234567890.
PHP
The underlying PHP implementation for arrays varies between different versions of PHP but its main difference with C’s own implementation is that it supports non-continuous integer keys and allows mixing them with string keys.
One can implement such an array either by using
- a binary search tree
search complexity: O(log n), access complexity (best case): O(n) - a hashtable
complexity: O(1).
Check out the Resources section for a set of related articles about hashtables (hash maps) and varying PHP implementations that take the topic more in detail.
<?php
$array = ["foo", "bar", "ohai"];
var_dump($array);
# array(4) { [0]=> string(3) "foo" [1]=> string(3) "bar" [2]=> string(4) "ohai" }
$array = ["a", "b", 6 => "c", "d"];
var_dump($array);
# array(4) { [0]=> string(1) "a" [1]=> string(1) "b" [6]=> string(1) "c" [7]=> string(1) "d" }
$array = [
1 => "a",
"1" => "b",
1.5 => "c",
true => "d"
];
var_dump($array);
# array(1) { [1]=> string(1) "d" }
$array = [
"Foo" => "Bar",
24 => 42,
"multi" => [
"dimensional" => [
"universe" => "what?"
]
]
];
var_dump($array["foo"]);
# Notice: Undefined index: foo in test.php on line 13
# NULL
var_dump($array["Foo"]);
# string(3) "Bar"
var_dump($array[24]);
# int(42)
var_dump($array["multi"]["dimensional"]["universe"]);
# string(5) "what?"
JavaScript
The JavaScript Array object is a global object that is used in the construction of arrays; which are high-level, list-like objects.
Arrays are list-like objects whose prototype has methods to perform traversal and mutation operations. Neither the length of a JavaScript array nor the types of its elements are fixed. Since an array’s length can change at any time, and data can be stored at non-contiguous locations in the array, JavaScript arrays are not guaranteed to be dense; this depends on how the programmer chooses to use them. In general, these are convenient characteristics; but if these features are not desirable for your particular use, you might consider using typed arrays.
Arrays cannot use strings as element indexes (as in an associative array), but must use integers. Setting or accessing via non-integers using bracket notation (or dot notation) will not set or retrieve an element from the array list itself, but will set or access a variable associated with that array’s object property collection. The array’s object properties and list of array elements are separate, and the array’s traversal and mutation operations cannot be applied to these named properties.
const fruits = ['Apple', 'Banana'];
console.log(fruits.length); // 2
const first = fruits[0]; // Apple
const last = fruits[fruits.length - 1]; // Banana
fruits.forEach(function(item, index) {
console.log(item, index);
});
// Apple 0
// Banana 1Common Lisp
In principle, an array in Common Lisp may have any number of dimensions, including zero. (A zero-dimensional array has exactly one element.) In practice, an implementation may limit the number of dimensions supported, but every Common Lisp implementation must support arrays of up to seven dimensions. Each dimension is a non-negative integer; if any dimension of an array is zero, the array has no elements.
An array may be a general array, meaning each element may be any Lisp object, or it may be a specialized array, meaning that each element must be of a given restricted type.
One-dimensional arrays are called vectors. General vectors may contain any Lisp object.
make-array dimensions &key element-type initial-element initial-contents adjustable fill-pointer displaced-to displaced-index-offset
=> new-array
Argument description:
dimensions list of dimensions, or non-negative integer
element-type a type specifier, default is T - any type
initial-element a value, default is implementation dependent
initial-contents an object
adjustable a generalized boolean, default is NIL
fill-pointer a valid fill pointer for the array, or T or NIL
displaced-to an array or NIL, default is NIL
displaced-index-offset a valid array row-major index for displaced arrays, default is 0
new-array an array
(make-array 5 :initial-element 'x) => #(X X X X X)
(make-array '(2 3) :initial-element 'x) => #2A((X X X) (X X X))
(length (make-array 10 :fill-pointer 4)) => 4
(array-dimensions (make-array 10 :fill-pointer 4)) => (10)
(make-array 10 :element-type 'bit :initial-element 0) => #*0000000000
(make-array 10 :element-type 'character :initial-element #\a) => "aaaaaaaaaa"
(let ((a (make-array '(2 2) :initial-element 'x :adjustable t))) (adjust-array a '(1 3) :initial-element 'y) a) => #2A((X X Y))
make-array '(4 2 3) :initial-contents
'(((a b c) (1 2 3))
((d e f) (3 1 2))
((g h i) (2 3 1))
((j k l) (0 0 0))))