A static array is a fixed length container containing n elements indexable from the range [0, n-1].
When and where is a static Array used:
- Storing and accessing sequential data.
- Temporarily storing objects.
- Used by IO routines as buffers.
- Lookup tables and inverse lookup tables.
- Can be used to return multiple values from a function.
- Used in dynamic programming to cache answers to subproblems. (knapsack and coin change problem)
|
Static Array |
Dynamic Array |
| Access |
O(1) |
O(1) |
| Search |
O(n) |
O(n) |
| Insertion |
N/A |
O(n) |
| Appending |
N/A |
O(1) |
| Deletion |
N/A |
O(n) |
The dynamic array can grow and shrink in size.
let a = [34, 4]
a.add(-7) // a = [34, 4, -7]
a.remove(-4) // a = [34, -7]
Q: How can we implement a dynamic array?
A: One way is to use a static array!
- Create a static array with an initial capacity.
- Add elements to the underlying static array, keeping track of the number of elements.