An array is a linear collection of data elements occupying a contiguous block of memory.
Arrays have two key characteristics:
- They have a fixed size, once created they cannot grow in size
- They can be randomly accessed, the indexer indicating the offset from the beginning of the allocated block of memory
🔔 Complexity is considered in terms of worst case.
| Insertion | Removal | Retrieval | Notes |
|---|---|---|---|
| Θ(n) | Θ(n) | Θ(1) |
TODO
A dynamic array wraps a real array, abstracting the re-allocation of contiguous memory.
When the underyling array reaches capacity, a larger block of memory is allocated and the original array is copied over.