# Array

Array is a data structure to store something in the computer's memory and do something to it. An array is like a list with some limitations and quirky things.

The picture above shows a simplified version of the computer's memory. The single memory addresses are marked as boxes.

An array represents a contiguous space in the computer's memory meaning when the array is
initialized a certain part of the memory is dedicated to the array.
The size of the box depends on the type.
In practice, it means we say the computer the following:
`"Give me memory space for 20 int type and I'll refer to myIntArray name"`

.

```
int[] myIntArray = new int[20];
```

An array is always fixed size, and its size has to be provided at initialization. The values of the array are set to highly probably null or default value of the type.

An array always zero indexed, meaning the first element is always under the index 0.

# Operations and their complexities in a single-thread environment

Operation | Time Complexity | Space complexity |
---|---|---|

Add/Append | `O(N)` |
`O(N)` |

Insert | `O(N)` |
`O(N)` |

Overwrite | `O(1)` |
`O(1)` |

Remove | `O(N)` |
`O(N)` |

Delete | `O(1)` |
`O(1)` |

Search | `O(N)` |
`O(1)` |

## Add/Append

Since the array is fixed size add/append operation includes resizing the array. The software engineer has to ensure that the resizing is executed successfully and contains the elements of the array, and the new, added, element is added as last one. This, from practical point of view, does not make a lot of sense, especially when the language, for example java or c# provides a variable size array data structure.

Add/Append operation **time complexity** is due to resize is `O(N)`

and **space complexity** is
`O(N)`

too as it requires allocating a new array.

## Insert

The key in the insert operation is that 1, the size of the data structure increases and 2, every item following the index to where the new item is inserted will be shifted right by one. As a result the software engineer has to pay attention to keep the original order of the elements, adding a new one, adding the shifted elements and that the new array has an increased size.

The two screenshots picture an insert operations where the `"five-2"`

value will be inserted
into the `6th`

index and everything after this index will be pushed right.
Since the array is already full there is no place for the last item to be shifted to.
It is either a silent data loss or some type of error message from the language runtime.

As a summary, we can say that in worst case the `insert`

operation requires going through the
array once.
In order to shift the array elements another array is needed with the same size as the
original array, in worst case.
As a conclusion, the time complexity of the `insert`

operation is **linear** in worst case.
The space complexity is also **linear**.

## Overwrite

From usage point of view when the code consist of `myIntArray[2] = 10`

it might seem we are
adding the `10`

to the array, but in reality we overwrite whatever is under the index `2`

by the value of `10`

.

A real add operation does not exist for an array without resize.

The code below show array initialization and that values under `3`

, `4`

, and `15`

are
overwritten by the provided values.

```
// initialization of the array
strin[] string_array = new[20];
// adding value 14 to the index 3 place in the array
string_array[3]="asd";
string_array[4]="foo";
string_array[15]="bar";
```

The code above results what is displayed in the screenshot below. Pay attention to the zero indexing.

Overwrite operation is a **constant** time operation since we know where is the value we
want to work with within the array (index).

## Remove

Remove operation is about removing the designated item and shifting all following elements in the array to left by one.

The screenshots below show the before and after state of the `remove`

operation.

When the item under index `7`

in the array gets removed all the elements following it
needs to be shifted left.
The last slot of the array, index `19`

, will have default value.

The worst case **time complexity** is `O(N)`

because every element in the array need to be
moved.
The worst case **space complexity** is `O(N)`

because the resizing portion of the operation
requires the allocation of another, similar size array.

## Delete

In reality, there is no such thing to remove an element from an array.
The `delete`

operation sets the value at the designated index to array default, which in
many cases `null`

.
The screenshots show this process.

```
string[] string_array = new[20];
string_array[6]=null;
```

The **time complexity** of this operation is `O(1)`

since we know the index of the element we
want to delete.
The **space complexity** of this operation is also `O(1)`

because overwriting the element
in the array does not require extra memory space.

## Searching for an element

Finding an element in the array means that every item in the array needs to be checked
if fits for the search criteria.
In general, it requires a `for`

or `foreach`

loop or something similar from the fancy
lamba functions.
But, the fact is that in worst case every element has to be checked.
It means that the time complexity of the search operation is **linear** while the space
complexity is **constant**.

# Considerations

When it comes to arrays worth to consider the followings:

- accessing elements is a fast operation, for this we have to know under which index is placed the element we wish to work with
- searching can be slow
- in general arrays don't have as rich api as, for example, an ArrayList (Java) or a List (C#)
- changing and managing the size of arrays is error-prone, slow and requires additional space
- the contiguous nature of array is a two-edged sword:
- it can give memory pressure to the system which has to find a place in the memory where the array can be fit. This can be made worse by some size management.
- due to cache locality 1, arrays can be faster than hashmaps if the array size is small, but this is a corner case, 2, in a streaming use case it can be advantageous