The Array: Your First Data Structure

A row of slots, side by side

An [[dsa-array|array]] stores its items in contiguous memory — one continuous block, each item in an equal-sized slot, with no gaps between them. Picture a row of identical mailboxes bolted together along a wall, numbered from 0. Because every box is the same size and they sit right next to each other, the address of box *i* is simple arithmetic: *start address + i × (size of one box)*. The computer doesn't search for box 5; it *calculates* exactly where it is and goes straight there.

index:     0     1     2     3     4
         +-----+-----+-----+-----+-----+
array:   |  17 |  42 |   8 |  99 |   5 |
         +-----+-----+-----+-----+-----+
          base  +1    +2    +3    +4   slots  (each the same size)

  v[3]?  address = base + 3 * slot_size  ->  go straight there  (O(1))

Indices start at 0. Because slots are equal-sized and adjacent, the address of any index is a single calculation — so reading v[3] is O(1), no matter how big the array is.

This is the array's superpower: random access in O(1). Whether the array holds 10 items or 10 million, fetching the item at a known index takes the same tiny, fixed amount of work — its [[time-complexity|time complexity]] doesn't grow with size. That single property is why arrays sit at the bottom of almost every other data structure you'll learn.

The catch: inserting in the middle is O(n)

The very thing that makes reads instant — no gaps — makes inserting painful. Suppose you want to slip a new value into the middle. There's no free slot there; the next item is jammed right up against it. So to make room, every item from that point to the end has to shift one place over. In the worst case (inserting at the front) you move *all n* items. Deleting from the middle is the mirror image: everything after the hole shifts back to close the gap. Both are O(n) — the work grows with the size of the array.

insert 7 at index 2:

before:  [ 17 | 42 |  8 | 99 |  5 |    ]
                       ^ everyone from here rightward must move
step:    [ 17 | 42 |    |  8 | 99 |  5 ]   shift 8,99,5 right
after:   [ 17 | 42 |  7 |  8 | 99 |  5 ]   now drop 7 into the gap

  -> up to n items shifted  ->  O(n)

To insert in the middle, every later item slides over by one. Inserting at the front moves all n items — that's why middle/front insert and delete are O(n).

Fixed arrays vs. the growable std::vector

A plain C++ array has a fixed size you must decide up front: `int a[5];` is exactly five slots, forever. If a sixth value shows up, there's no room. That's fine when you know the count in advance, but real programs often don't. The fix is a [[dynamic-array|dynamic array]]: an array that can *grow* when it fills up. In C++ that's `std::vector`, and it's the workhorse you'll reach for constantly.

#include <vector>

int a[5] = {17, 42, 8, 99, 5};   // fixed: exactly 5 slots, no growing
int x = a[3];                     // O(1) read -> 99

std::vector<int> v = {17, 42, 8}; // dynamic: starts at 3, can grow
v.push_back(99);                  // append at the end (usually cheap)
v.push_back(5);                   // now {17, 42, 8, 99, 5}
int y = v[3];                     // O(1) read, same as the plain array

A fixed array can't grow; std::vector can. Both give O(1) indexing — vector keeps the array's superpower while letting you push_back freely.

How does it grow? When a vector fills up, it quietly grabs a bigger block of memory (typically twice the size) and copies the items over. That copy sounds expensive — and once in a while it is — but because the size *doubles* each time, those costly moments are rare and spread thin. Averaged over many `push_back`s, appending behaves as if it were O(1). You don't need the full accounting yet; just trust that `std::vector` gives you a growable array without giving up the instant O(1) read.