Data structure choice is "what shape gives my access pattern the right cost." A naive list is fine for 100 items; not for 10 million. A hash table is fast for lookup; useless for ordered scan. Trees mediate.
This page is the everyday-engineering catalogue. For deeper dives, see the per-structure pages.
The default. Contiguous memory; O(1) random access by index; O(n) insert / delete in the middle.
| Operation | Cost |
|---|---|
arr[i] | O(1) |
arr.append(x) | Amortised O(1) |
arr.insert(i, x) | O(n) |
arr.remove(x) | O(n) |
| Iteration | O(n), cache-friendly |
Hidden virtues: cache locality. Iterating an array is far faster than iterating a linked list of the same size because elements are sequential in memory. Modern CPUs prefetch sequential data; random pointer chasing kills throughput.
Use when: ordered iteration matters; size is bounded; random access by position needed; the sequence isn't constantly modified in the middle.
Each node points to the next (and possibly previous). O(1) insert/delete given a pointer to the node; O(n) random access.
In modern code, you rarely want a linked list. The cache-locality penalty makes them slower than arrays for almost everything. Use only when:
For most "linked list use cases," dynamic arrays (Python list, Java ArrayList, C++ vector) are faster.
The workhorse. O(1) average-case lookup, insert, delete by key. Unordered.
| Operation | Average | Worst case |
|---|---|---|
m[k] | O(1) | O(n) |
m[k] = v | O(1) | O(n) |
del m[k] | O(1) | O(n) |
| Iteration | O(n) | O(n) |
Worst case is bad-hash collision; modern hash maps with universal hashing avoid this in practice.
Implementation specifics matter:
For 99% of use cases, the language's standard hash map is the right choice.
Use hash maps for: lookup by key without ordering; sets (use as a map with dummy values); de-duplication; building indexes.
Balanced binary search trees (red-black tree, AVL tree, B-tree-flavoured): O(log n) lookup, insert, delete, with the ability to iterate in sorted order.
| Operation | Cost |
|---|---|
| Lookup, insert, delete | O(log n) |
| Range query [a, b] | O(log n + matches) |
| Iteration | O(n), in sorted order |
Languages: Java TreeMap, C++ std::map, Python sortedcontainers.SortedDict, Rust BTreeMap.
Use when: range queries matter; you need ordered iteration; you need both fast lookup and sorted access.
For massive datasets, B-trees (used in databases) outperform balanced binary trees because their fan-out matches disk / cache page sizes. See BalancedSearchTrees, DatabaseIndexingStrategies.
A binary heap supports O(log n) insert and O(log n) extract-min (or extract-max). O(1) peek.
| Operation | Cost |
|---|---|
| Insert | O(log n) |
| Peek | O(1) |
| Extract-min | O(log n) |
| Decrease-key | O(log n) (with bookkeeping) |
Used for: priority queues, top-k selection, event simulation, Dijkstra's algorithm, scheduling.
Languages: Python heapq, Java PriorityQueue, C++ std::priority_queue, std::make_heap.
Variants:
Use a binary heap unless you have a specific reason to deviate.
Stack: LIFO; push, pop both O(1). Backed by an array. Queue: FIFO; enqueue, dequeue both O(1). Usually a deque or circular buffer.
Languages provide these directly. Stacks are heavily used in DFS, expression evaluation, recursion replacement. Queues in BFS, message processing.
Don't use a LinkedList to implement a stack or queue when the language has a deque. Cache-friendlier; faster.
A set is a hash map with no values, or a sorted map with no values. Same complexity. Used for membership tests, deduplication, intersection / union / difference.
For approximate membership at huge scale, see BloomFilters.
Tree structures keyed on character sequences. Excellent for prefix queries.
See TrieDataStructure.
A graph is a collection of nodes and edges. Representations:
Maintains a partition of elements. Supports union(x, y) and find(x). With path compression and union by rank: practically O(α(n)) per operation, where α is the inverse Ackermann function (basically constant).
Used for: connected components, Kruskal's MST, percolation, image segmentation.
Probabilistic alternative to balanced trees. O(log n) expected for lookup, insert, delete. Used in Redis sorted sets, some database indexes.
Simpler to implement than balanced trees; competitive performance.
Probabilistic membership test. False positives possible; false negatives impossible. Tiny memory.
See BloomFilters.
For substring queries on a text. O(query length) lookups regardless of text length. Used in genome alignment, log analysis.
A hash map + doubly-linked list. O(1) get, put, eviction. Used for caches.
Most languages have library implementations (Python functools.lru_cache, Java LinkedHashMap, etc.).
Generalisation of balanced binary trees with high fan-out. Used in databases for on-disk indexes. See DatabaseIndexingStrategies.
Average-case bounds (e.g., O(1) hash map insert) ignore that occasionally an insert is slow (rehash). For most application code this is fine; for real-time systems with strict latency bounds, worst-case matters.
Languages let you check or pre-allocate: Python dict doesn't expose this; Java ArrayList has ensureCapacity; you can resize-then-fill to avoid amortised costs at hot paths.
For very performance-sensitive code:
These optimisations matter in hot loops; don't matter in 99% of application code. Profile before micro-optimising.
For most application code:
Knowing the catalogue is what lets you pick the right one. The catalogue is what this page tries to be.