Dynamic array
One of the most commonly used data structures, it is a growable/shrinkable contiguous list of elements.
| Pros | Cons |
|---|---|
| Has similar performance for array but is still growable | If it has to grow, it will take O(n) time to create a larger array and copy the data over |
| Fast random access/indexing to elements | Non-optimal performance when inserting/deleting from middle of array |
| Contiguous elements lead to good locality of reference and cach |
Implementations
Java: ArrayList
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
Python: List
collection = [1, 2, 3]
collection.append(4)
C++: Vector
std::vector<int> v = { 1, 2, 3};
| Operations | Worst | Average |
|---|---|---|
| Delete (Beginning/Middle) | O(n) | |
| Delete (End) | O(1) | |
| Index | O(1) | |
| Insert (Beginning/Middle) | O(n) | |
| Insert (End) | O(1) |
