Picking a structure by its dominant operation
The right data structure depends on which operation you do most: random access, searching, or inserting and deleting. This reference lists the Big-O time complexity for each of those operations across the common structures — arrays, linked lists, hash tables, trees, heaps and graphs — plus their space cost. Search by keyword and highlight the operation you care about.
Quick comparison table
| Structure | Access | Search | Insert | Delete | Space |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | O(n) |
| Linked list | O(n) | O(n) | O(1)* | O(1)* | O(n) |
| Hash table | — | O(1) avg | O(1) avg | O(1) avg | O(n) |
| Balanced BST | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Binary heap | O(1) min/max | O(n) | O(log n) | O(log n) | O(n) |
| Graph adj. list | — | O(V+E) | O(1) | O(V+E) | O(V+E) |
| Graph adj. matrix | — | O(1) edge | O(V²) | O(V²) | O(V²) |
*Linked list insert and delete are O(1) only when you already hold a reference to the node. Finding the node first takes O(n).
Average-case figures assume good conditions (low hash load factor, balanced tree). Structures that can degrade — hash tables at high load, unbalanced BSTs — are noted in the full reference.
Choosing between the common options
Array vs linked list — use an array when you need indexed access (O(1)) or cache-efficient iteration (arrays are contiguous in memory). Use a linked list when you frequently insert or delete in the middle and already hold the node, since that is O(1) versus O(n) for an array’s element shifting.
Hash table vs balanced BST — hash tables give O(1) average for lookup, insert, and delete but provide no ordering. A balanced BST (AVL, red-black) guarantees O(log n) worst-case for all operations and keeps keys sorted, enabling range queries and ordered iteration. Use a hash table for pure membership or lookup; use a BST when you also need order.
Heap — the heap only exposes the minimum (or maximum). It is the right structure for a priority queue: O(1) peek at the extremum, O(log n) push and pop. It is not suitable for arbitrary membership tests, range queries, or random access.
Graph representation — adjacency lists use O(V+E) space and are efficient for sparse graphs; edge traversal is O(degree). Adjacency matrices use O(V²) space but give O(1) edge lookup — worthwhile only when the graph is dense and you need fast edge existence checks.
Common mistakes
- Using a plain BST (not self-balancing) and inserting sorted data — degrades to O(n) per operation because the tree becomes a linked list.
- Choosing an array for frequent mid-sequence inserts — every insert shifts O(n) elements.
- Using a hash table when you need to iterate in sorted key order — requires a sort step afterward.
- Allocating a full adjacency matrix for a graph with thousands of nodes but few edges — wastes O(V²) memory for mostly-zero entries.