Unordered (unsorted) array

Array:
-  is a collection of data items (its elements) of the same type arranged contiguously in memory
- can be sorted or unsorted
- can accept or not duplicate values

Array is created with predefined size =>
   - if there are less elements than the array size is => memory waste
   - if there are more elements that the array size is => program fails

Implementations:
- C-style array
- std::vector

Unordered arrays with no duplicates

Operations:

Insertion

- Algorithm: always at the end (at the first vacant position); it must be checked whether item already exists in the array - a search is performed
- Complexity: O(N) (because of the search)

Search for a given item (lookup)

- Algorithm: linear search - starts at the beginning and goes through all items till item is found
- Complexity: O(N)

Deletion of a given item

- Algorithm: item must be found first; once its found and removed, all subsequent elements must be shifted down one position (towards the beginning of the array) in order to fill the gap and maintain contiguity of elements in memory
- Complexity: O(N) for search + O(N) for shifting = 2 * O(N) ~ O(N)

Unordered arrays with duplicates

Operations:

Insertion

- Algorithm: always at the end (at the first vacant position)
- Complexity: O(1)

Search for a given item (lookup)

- Algorithm: linear search - starts at the beginning and goes through all items till item is found
- Complexity: O(N)

Deletion of a given item

- Algorithm: item must be found first; once its found and removed, all subsequent elements must be shifted down one position (towards the beginning of the array) in order to fill the gap and maintain contiguity of elements in memory
- Complexity: O(N) for search + O(N) for shifting = 2 * O(N) ~ O(N)