Unit 01
Arrays & Strings
The simplest way to hold many values: a fixed block of memory where every item sits at a known distance from the start. Almost every other structure either builds on this or exists to work around its limits.
// elements sit contiguously in memory, so any index is a direct lookup
What it is
An array stores a fixed-size, ordered collection of elements in one continuous block of memory. Because every element is the same size, the computer can calculate exactly where any element sits just from its index, without having to look at anything else first. A string is, under the hood, usually just an array of characters.
Why it's useful
- Fast access by position. Reading
arr[5]takes the same time whether the array has 10 elements or 10 million. - Memory efficient. No extra bookkeeping is needed for each element, unlike structures that store pointers alongside data.
- Cache friendly. Because elements sit next to each other, scanning through an array in order tends to be fast on real hardware.
Where it struggles
- Fixed size. Most array types can't grow once created — adding one more element than fits means creating a new, bigger array and copying everything over.
- Costly middle insertions. Inserting or deleting in the middle means shifting every element after it.
Time complexity
| Operation | Time |
|---|---|
| Access by index | O(1) |
| Search (unsorted) | O(n) |
| Insert / delete at end | O(1) |
| Insert / delete in middle | O(n) |