A vector is a dynamic array: a resizable collection stored contiguously in memory. It may reserve extra capacity so insertions do not require resizing every time. section 1.1
Key tradeoffs shape when a vector is useful:
- Index-based access is O(1), because elements occupy predictable contiguous positions. section 1.1
- Appending is O(1) on average, but O(n) when extra capacity is exhausted and elements must be copied into a new array. section 1.1
- Compared with linked lists, vectors provide direct access and avoid per-node pointer overhead, but insertion flexibility differs. section 1.1
Common implementations
The same dynamic-array idea appears as ArrayList in Java, std::vector in C++, and slices in Go. section 1.1













