What are Data Structures and why are they important?
Updated Feb 20, 2026
Short answer
A data structure is a way of organising data in memory so that particular operations are efficient. They matter because the structure you choose determines the time and space cost of everything you do with that data — the same task can be instant with one structure and unusably slow with another, and no amount of micro-optimisation compensates for the wrong choice.
Deep explanation
Every data structure trades one operation's cost against another's. There is no best structure — only one best suited to your access pattern.
| Structure | Access | Search | Insert | Delete | Trades away |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | Cheap insertion |
| Linked list | O(n) | O(n) | O(1)* | O(1)* | Random access, cache locality |
| Hash table | — | O(1) avg | O(1) avg | O(1) avg | Ordering, worst-case guarantees |
| Balanced BST | O(log n) | O(log n) | O(log n) | O(log n) | Constant-factor speed |
| Heap | O(1) min/max | O(n) | O(log n) | O(log n) | Arbitrary search |
\* given a reference to the node.
Choosing well means starting from the operations you perform most:
- Membership tests dominate → hash set.
- Need sorted order or range queries → balanced tree, not a hash table.
- Repeatedly need the smallest item → heap.
- Index-based access with mostly appends → dynamic array.
The impact is not marginal. Checking membership in a 100,000-element list is a linear scan; the same check against a hash set is a single lookup. Run that inside a loop over another 100,000 items and the difference is ten billion operations versus a hundred thousand — minutes against milliseconds.
Constant factors and memory layout matter too. Arrays are contiguous and prefetch well, so a linear scan of a small array often beats a linked list's theoretically superior insertion, because cache misses dominate at small sizes.
Real-world example
A batch job reconciles 50,000 incoming payment records against 200,000 known transaction IDs.
# O(n*m) — for every record, scan the whole list. ~10 billion comparisons.known = load_transaction_ids() # list of 200,000 stringsfor record in incoming: # 50,000 records if record.txn_id in known: # O(200,000) linear scan each time reconcile(record)One line changes the complexity class:
known = set(load_transaction_ids()) # build once, O(m)for record in incoming: if record.txn_id in known: # O(1) average reconcile(record)Same logic, same output — from roughly 10¹⁰ comparisons to 2.5×10⁵. In practice this is the difference between a job that runs for an hour and one that finishes before you've switched windows.
Common mistakes
- - Reaching for a list by default and only reconsidering after something is measurably slow.
- - Using a hash table where ordering or range queries are required, then sorting the keys on every access and losing the benefit.
- - Repeatedly calling an O(n) operation inside a loop — `list.insert(0, x)` or string concatenation in a loop — turning linear work into quadratic.
- - Reciting Big-O while ignoring constant factors and cache behaviour
- for a handful of elements a linear array scan usually beats a 'faster' structure.
- - Forgetting that hash tables degrade to O(n) in the worst case with adversarial or poor-quality hash functions.
- - Optimising the structure before knowing the access pattern
- the right choice follows from what you do most, not from which structure sounds most sophisticated.
Follow-up questions
- When would you choose a linked list over an array?
- Why can a hash table degrade to O(n)?
- What structure would you use for autocomplete?
- How do you decide between a heap and a sorted array for priority work?