Array
Array is contiguous area of memory consisting of equal-size elements indexed by contiguous integers.
- Constant-time access to any element.
- Constant time to add/remove at the end.
- Linear time to add/remove at any arbitrary location.
| . | Add | Remove |
|---|---|---|
| Beginning | O(n) | O(n) |
| End | O(1) | O(1) |
| Middle | O(n) | O(n) |
There are diffrent types of arrays.
1. Static Array
- size of the array is not changable.
2. Dynamically-allocated Array
- max size of the array should be declared when allocating an array.
3. Dynamic / Resizable Array
- Unlike static arrays, it can be resized.
- Appending a new element is often constant time, but can take O(n).
- Some space is wasted.
It has the following operations:
- Get(i): returns element at location i
- Set(i, val): sets element i to val
- PushBack(val): adds val to the end
- Remove(i): removes element at location i
- Size(): returns the number of elements
Common Implementation
- C++: vactor
- Java: ArrayList
- Python: list (the only kind of array)
Note that there are no static arrays in Python. They are all dynamic arrays.
| operations | Runtime |
|---|---|
| Get(i) | O(1) |
| Set(i, val) | O(1) |
| PushBack(val) | O(n) |
| Remove(i) | O(n) |
| Size() | O(1) |
