Array

An array is a data structure representing a collection of items of the same type. The underlying memory for arrays is a contiguous block in memory. Elements of arrays can be accessed through an index.

Arrays can have dimensions, by which we mean an array within an array is a two dimensional array.

Properties

Arrays can be zero indexed or one indexed. Most programming languages 0 indexes them. Lua for example is an exception.

Arrays have a different measure of capacity and size in the case of dynamically sized arrays. For example, an array can be of capacity eight, but of size 5, wasting 3 bytes (for an array of chars for example).

Resizing

There are two possible types of arrays, static or dynamic arrays. Static arrays have a fixed size at compile time, and as such can be statically allocated. Those arrays cannot be resized, therefore elements cannot be inserted or removed, though they are still mutable.

Dynamic arrays have the capacity to resize, grow and shrink in capacity. Generally, this is done through a resizing mechanic that will grow the capacity of the array above a certain threshold, and will shrink it below a certain threshold. The exact numbers vary per implementation. This enables the insertion and deletion of items.

Let the threshold for array resizing be full capacity for growth, and 1/4 capacity for shrinking. Once we have a full array and we insert another item, the array copies itself to another array of twice the capacity. This is an $O(n)$ operation, however because it happens only on resize, the amortized time complexity of an insertion for dynamic arrays is still $O(1)$. If the array shrinks to only 1/4 capacity, then it does the same thing but copies itself to another array of half the size.

Efficiency

Static arrays are extremely efficient in terms of access and space usage. An indexed access of an element in an array is always $O(1)$, and they take up $0$ extra space. However as mentioned before this comes at the cost of flexibility.

Dynamic arrays are also quite efficient, but take up more space than statically allocated arrays to give enough space to still be amortized $O(1)$ insertion.

	Indexed access	Insert (beginning of array)	Insert (middle)	Insert (end)	Wasted Space
Static Array	$O(1)$	N/A	N/A	N/A	$0$
Dynamic Array	$O(1)$	$O(n)$	$O(n)$	$O(1)$ amortized	$O(n)$

Note that the exact amount of wasted space depends on the implementation of the resizing, but it is of the order of $O(n)$.

Access

Arrays can be accessed through the [] notation, but also through the pointer dereference * notation, like so:

arr[4];
*(arr + 4);
//Careful, the above is not equal to:
*arr + 4;

Note that line 4 would dereference arr, then add 4 to whatever value is in arr\[0] , because of operator precedence in C.

Examples

Static Arrays in C

In C and C++ static arrays are declared by passing a number of elements in between brackets after the type and name of the variable.

int arr[10];

This can be extended to multi-dimensional arrays as follows:

int arr[10][10];

Remember that in C and C++, default initialization does nothing, i.e. both of those arrays would currently contain garbage values.

This can be combined into one declaration using the bracket initialization syntax:

int arr[5] = {0, 1, 2, 3, 4};
//or
int arr[5] = {0};

On line 3, that would initialize all elements of the array to zero.

Dynamic Arrays

Dynamic arrays do not exist in C, but they do in C++, under the name std::vector. In C, you would need to manually implement them from scratch.

std::vector<int> v = {0, 1, 2, 69};

This array will resize automagically.