FREE LESSON · Algorithms & data structures · 1 OF 4
How to Choose the Right Data Structure
A data structure is a bet — Choose for operations, constraints, and evidence
Layout determines which questions are cheap.
An array buys constant-time indexing and locality but makes middle insertion expensive. A hash table buys expected constant-time key lookup but gives up natural ordering and needs a collision policy. A balanced tree keeps ordered operations logarithmic. A heap exposes only the next priority cheaply. The workload—not the name—decides.
Start with dominant operations, scale, ordering, mutation, memory, and worst-case requirements.
Hash lookup has a contract behind “O(1)”
A hash function maps keys to buckets; collisions must be resolved; the table must keep load controlled through resizing or another policy. Expected constant time assumes hashes distribute the actual keys well and adversaries cannot force pathological clustering. Equality still confirms the key.
Complexity statements have assumptions. Write them next to the bound.