Arrays
An array is a basic data structure storing an ordered collection of elements, often at contiguous memory addresses. Each element is directly accessible by an array index (usually starting with 0).
| Operation | Average | Worst |
|---|---|---|
| Access | $\htmlClass{text-green}{\Theta(1)}$ | $\htmlClass{text-green}{\mathcal{O}(1)}$ |
| Insert | $\htmlClass{text-yellow}{\Theta(n)}$ | $\htmlClass{text-yellow}{\mathcal{O}(n)}$ |
| Delete | $\htmlClass{text-yellow}{\Theta(n)}$ | $\htmlClass{text-yellow}{\mathcal{O}(n)}$ |
Static arrays
A static array is allocated with a predetermined capacity, which is the maximum number of elements the array can hold. The size of the array refers to the actual number of elements it stores, which may be less than the capacity.
Dynamic arrays
The fixed-capacity limitation of static arrays can be overcome by resizing the array when adding a new element would result in exceeding the array’s capacity.
To resize the array, a new static array is allocated with a larger capacity (e.g. 2 times the previous capacity). Then, each element from the original array is copied to the new array, after which the original can be discarded.
Dynamic arrays are commonly used to implement lists .
Operations
Access
The time complexity of array access is constant – given a contiguously allocated array, the memory address of an element can be directly computed from the index:
$$ \text{address} = \text{starting address} + (\text{index} \times \text{element size}) $$
Insertion
The best-case scenario for insertion is appending an element at the end of the array, because it does not require shifting any of the existing elements:
The worst-case scenario for insertion is prepending an element at the start of the array, because it requires shifting each subsequent element toward the end of the array:
Deletion
The best-case scenario for deletion is deleting the last element of an array, because it does not require shifting any of the remaining elements:
The worst-case scenario for deletion is deleting the first element of an array, because it requires shifting each remaining element toward the start of the array:
