A data structure is not just a named container. It is a way to represent information and a contract about the operations that representation supports. Choosing one means choosing which work will be cheap, which work will be expensive, and what assumptions make the trade-off valid.
Contiguous and linked storage
A dynamic array stores elements next to each other. Indexing is constant time, and sequential iteration uses memory with good spatial locality. Appending is usually constant time, but an occasional resize allocates a larger region and copies the old elements. A linked list can insert or remove a known node without shifting a suffix, but reaching that node requires pointer chasing. The list's nominal O(1) insertion does not make finding the insertion point O(1).
Hash tables and ordered trees
A hash table maps a key to a bucket using a hash function. Collisions require a policy such as chaining or probing. Under suitable hashing and load-factor assumptions, lookup is expected O(1), but the operation is not guaranteed to take one probe and it does not preserve sorted order. A balanced search tree keeps keys ordered and supports range queries and predecessor/successor operations in O(log n), at the cost of multiple dependent pointer reads and maintenance during updates.
Match the structure to the question
Use a heap when you repeatedly need the current minimum or maximum, not when you need arbitrary ordered traversal. Use a graph representation that matches the expected operations: adjacency lists are compact for sparse graphs, while an adjacency matrix makes edge-existence checks direct at O(V²) space. A Bloom filter can answer “definitely absent” or “possibly present” using little memory, but it permits false positives and cannot recover stored values.
Include the machine in the explanation
Big-O compares growth rates; it does not count cache misses, allocator work, key comparison cost, or memory overhead. If a workload scans most elements, contiguous layout may beat a theoretically cheaper pointer-heavy operation. Measure the actual workload after checking that the structure's semantic guarantees match what the program needs.
OpenDSA's data-structure material provides interactive explanations and exercises to pair with these trade-offs.