Data Structures
Lessons · #1 of 11

Arrays

Contiguous memory — index access in one CPU cycle

init

Try it: Tap read to flash an index (green = O(1)). Then insert at an early index and watch the right-hand cells ripple-shift orange — that is O(n) cost made visible.

Why it matters

Arrays are the most fundamental data structure in computing. Every other data structure is either built on arrays or designed to overcome their limitations. Understanding arrays means understanding how computers actually store and access data.

The idea

Imagine a row of numbered lockers in a hallway. Each locker has a number (index) painted on it, and you can instantly walk to locker #47 because you know exactly where it is - you don't need to check lockers 1-46 first.

That's an array. A contiguous block of memory where each slot has a fixed position.

The magic: because elements are stored side-by-side, accessing any element by its index is instant - O(1). The computer calculates: base_address + (index * element_size).

The limitation: if you want to insert a new element in the middle, everything after it must shift over - O(n). Like inserting a book on a tightly packed shelf.

Key takeaways

Going deeper

Arrays shine when you need random access and rarely insert/delete in the middle. Dynamic arrays (Vec, ArrayList) handle resizing by doubling capacity when full - this makes the amortized cost of append still O(1). Arrays are also cache-friendly: accessing sequential elements is fast because they're loaded into CPU cache together.

Why "amortized" O(1) — the doubling proof

A dynamic array starts with some small capacity (say 4) and doubles every time it fills up. Most push calls just write into a free slot — O(1). But every so often, you fill the array and have to allocate a new one twice as big and copy n items over — that's O(n).

So is push really O(1)? On average across many pushes, yes. Count the total work to grow from 1 to n elements:

copies: 1 + 2 + 4 + 8 + … + n/2 + n
     = 2n − 1
     = O(n) total work spread across n inserts
     = O(1) per insert, amortized

The geometric sum doubles each term but the previous terms shrink to half. Total work stays linear in n. If you halve instead of double, every resize is O(n) and you don't get the amortization payoff — total work climbs to O(n²). Doubling is the magic constant that makes the books balance.

This is the canonical first taste of amortized analysis — the same pattern shows up in hash-table rehashing, heap construction, and ring-buffer queues.

Cache locality — the order-of-magnitude reason

Arrays aren't fast just because of O(1) access — they're fast because modern CPUs prefetch sequential memory. When you read arr[i], the CPU loads a full cache line (typically 64 bytes — 16 ints, or 8 doubles) into the L1 cache. Reading arr[i+1] then arr[i+2] are free cache hits.

A linked list with the same data scattered across memory pays an L1 miss on most pointer dereferences. The constants:

On a hot loop, an array can be 10–100× faster than a linked list holding the same elements, even though both are O(n) to iterate. Big-O hides this. The robotics rule of thumb: prefer arrays of structs (AoS) or struct-of-arrays (SoA) for any inner loop; reserve linked lists for the rare case where you need O(1) splice with a live node reference.

Math details

Time Complexity
Access: O(1)
Search (unsorted): O(n)
Insert at end: O(1) amortized
Insert at index i: O(n-i)
Address Calculation
address[i] = base + i × sizeof(element)

Implementation

Array in Rust

// Fixed-size array
let arr: [i32; 5] = [1, 2, 3, 4, 5];
let third = arr[2]; // O(1) access

// Dynamic array (Vec)
let mut vec = Vec::new();
vec.push(1); // O(1) amortized
vec.insert(0, 0); // O(n) - shifts all elements

Key Operations

Practice

Three classic problems built on arrays, each demonstrating a different technique:

→ Browse all practice problems