Arrays

The problem

You're building a weather logger. Every second a sensor spits out a temperature reading, and by the end of the day you have a million of them. Later, someone asks: "What was the temperature at reading number 750,000?" You want that answer instantly — not after the program grinds through three-quarters of a million values first.

So the question isn't just "where do I put a million numbers?" It's "where do I put them so that jumping to any one of them costs the same tiny amount of work, whether it's the first or the last?"

A first attempt

Imagine you stored each reading in a little box, and each box only knew where the next box was — a chain. To reach reading 750,000 you'd start at box 0 and follow the chain 750,000 times. Grabbing "any one instantly" becomes a walk of O(n) steps. The bigger the log, the slower the lookup. That's exactly the trap we wanted to avoid.

The chain wastes something: it never uses the fact that our readings have a fixed size and could sit right next to each other in memory.

The insight

Put every element in one contiguous block of memory, each the same size. Now the address of element i is pure arithmetic:

address(i) = base_address + i × element_size

No walking. One multiply, one add, and you're standing on element i. That's an array, and that constant-time jump is called random access. The catch: because everything is packed tight, inserting in the middle means shifting everything after it to make room.

How it works

index:    0    1    2    3    4
        ┌────┬────┬────┬────┬────┐
value:  │ 12 │ 15 │  9 │ 22 │ 30 │
        └────┴────┴────┴────┴────┘
insert 99 at index 2 → 9, 22, 30 all shift right (O(n))

The code

readings = [12, 15, 9, 22, 30]

# Random access — O(1), no scanning
print(readings[3])          # 22

# Insert in the middle — O(n), everything after shifts right
readings.insert(2, 99)      # [12, 15, 99, 9, 22, 30]

const readings: number[] = [12, 15, 9, 22, 30];

// Random access — O(1)
console.log(readings[3]);      // 22

// Insert in the middle — O(n)
readings.splice(2, 0, 99);     // [12, 15, 99, 9, 22, 30]

int[] readings = {12, 15, 9, 22, 30};

// Random access — O(1)
System.out.println(readings[3]);   // 22

// A fixed array can't grow, so inserting means copying into a bigger one — O(n)
int[] bigger = new int[readings.length + 1];
int pos = 2;
for (int i = 0; i < pos; i++) bigger[i] = readings[i];
bigger[pos] = 99;
for (int i = pos; i < readings.length; i++) bigger[i + 1] = readings[i];
// bigger = {12, 15, 99, 9, 22, 30}

#include <stdio.h>

int main(void) {
    int readings[6] = {12, 15, 9, 22, 30};  // one extra slot for growth
    int size = 5;

    printf("%d\n", readings[3]);   // 22 — O(1) access

    int pos = 2;
    for (int i = size; i > pos; i--)   // shift right — O(n)
        readings[i] = readings[i - 1];
    readings[pos] = 99;
    size++;                            // {12, 15, 99, 9, 22, 30}
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> readings = {12, 15, 9, 22, 30};

    cout << readings[3] << "\n";               // 22 — O(1) access

    readings.insert(readings.begin() + 2, 99); // O(n) shift
    // {12, 15, 99, 9, 22, 30}
    return 0;
}

Complexity

When to use it

Practice

Recap

• An array is one contiguous block of equal-sized slots, so arr[i] is a constant-time address computation — O(1) random access.
• The price of that packing is O(n) insertion and deletion in the middle, because later elements have to shift.
• Dynamic arrays hide fixed capacity by doubling and copying, giving amortized O(1) appends.