Array basics
Written by haloboy777 on 2023-11-17
Basic explanation of arrays and various nuances
Definition: Arrays is a data structure that is structured as a contiguous memory spaces for data values.
Types
- Static arrays
- Dynamic arrays
Common operations
- Access
- Set
- Traverse/Search
- Copy
- Insert
- at beginning
- at end
- somewhere in middle
- Remove
- at beginning
- at end
- somewhere in middle
Big O
| Action | Time | Space |
|---|---|---|
| Access | O(1) | O(1) |
| Set | O(1) | O(1) |
| Traverse/Search | O(n) | O(1) |
| Copy | O(n) | O(n) |
| Insert | ||
| at the beginning | O(n) | O(1) |
| at the end | O(1) | O(1) |
| somewhere in middle | O(n) | O(1) |
| Remove | ||
| at the beginning | O(n) | O(1) |
| at the end | O(1) | O(1) |
| somewhere in middle | O(n) | O(1) |