Data Structures
A data structure is a representation plus invariants that make a set of operations efficient. Choose one from the workload—not from a generic ranking of “advantages” and “disadvantages.”
Start with operations
| Need | Typical representation | Strength |
|---|---|---|
| Random positional access | array / dynamic array | indexing, locality |
| Local insertion with a known node | linked list | pointer rewiring |
| Last-in, first-out access | stack ADT | one-ended discipline |
| First-in, first-out access | queue ADT | ordered processing |
| Exact key lookup | hash table | expected constant-time lookup |
| Ordered keys and ranges | balanced search tree | logarithmic ordered operations |
| Repeated minimum/maximum | heap | logarithmic updates, constant root access |
| Arbitrary relationships | graph representation | traversal and path algorithms |
Representation versus interface
A stack or queue is an abstract data type: its contract restricts which element may be removed. It can be implemented by an array, linked nodes, or another container. An array and linked list instead describe storage organization.
Questions to ask
- Which operations dominate, and what are their worst or amortized costs?
- Must references, indexes, or iteration order remain stable after mutation?
- Is capacity bounded, and is allocation allowed during operation?
- How important are cache locality and per-element overhead?
- Are concurrency, persistence, or ownership part of the contract?
Asymptotic costs are necessary but incomplete: two operations can differ substantially in allocation, indirection, and locality.