Why the choice comes first
A data structure is just a way of arranging data in memory. That arrangement quietly fixes the price of every operation you will run — lookup, insert, delete, scan. Pick the wrong one and no amount of clever logic saves you; pick the right one and the slow problem simply disappears. So the question is never “which structure is best” — it is “which operations do I do most, and which structure makes those cheap.”
The everyday four
- Array / list — ordered items by position. Instant access by index, cheap to append, expensive to insert or search in the middle.
- Hash map / dictionary — key → value. Near-instant lookup, insert and delete by key. No order. The workhorse of real code.
- Set — a hash map with keys only. Instant “have I seen this?” and automatic de-duplication.
- Stack / queue — controlled ends. Stack is last-in-first-out (undo, recursion); queue is first-in-first-out (job pipelines, breadth-first search).
Match the structure to the access pattern
Looking things up by an id thousands of times? A hash map, not a list you scan. Checking membership? A set. Always need the smallest item next? A heap. Order matters and you insert in the middle a lot? A linked list or a balanced tree. The pattern of your reads and writes is the spec — the structure is the answer to it.
The cost, roughly
- Array — index: O(1) · search: O(n) · insert middle: O(n).
- Hash map / set — lookup / insert / delete: O(1) average.
- Balanced tree — lookup / insert / delete: O(log n), and stays sorted.
- Heap — peek min/max: O(1) · insert / pop: O(log n).
Rule of thumb
Reach for a hash map by default — most “this is slow” bugs are a linear scan that should have been a key lookup. Use an array when order or position matters, a set when you only care about presence, a tree when you need data sorted and changing, a queue or stack when the order of processing is the whole point. Choose the structure first; the code gets easy after.