Choosing a Data Structure

An abstract data type (ADT) specifies a contract — the operations a client can invoke (insert, delete, search, min, successor, union) — without prescribing an implementation. A data structure is a concrete realization of that contract, with specific complexity guarantees attached to each operation. The central insight of this article is that no data structure is best; each is Pareto-optimal for some slice of the operation-frequency space, and the engineering task is to identify which slice your workload occupies. Formally, think of a workload as a vector of operation frequencies: $(f_{\text{search}}, f_{\text{insert}}, f_{\text{delete}}, f_{\text{min}}, f_{\text{range}}, f_{\text{successor}}, \dots)$, together with a distribution over keys (uniform random, adversarial, skewed/Zipfian, already sorted, streaming). The expected cost of running the workload on structure $S$ is

where $T_S(\text{op})$ is the structure's cost (worst-case or expected, depending on what you need to guarantee) for that operation. Choosing a data structure is choosing $S$ to minimize this cost subject to the guarantees your system must uphold — e.g., a real-time system cannot accept "amortized $O(\log n)$," it needs worst-case per-operation bounds. Three families dominate practical use, and each buys speed by sacrificing something else. Sequential structures (arrays, linked lists, dynamic arrays) are simple and cache-friendly but support at most one of {fast random access, fast insertion/deletion} well. Hash-based structures flatten the key space via a hash function to get expected $O(1)$ search/insert/delete, but abandon order — there is no efficient "find the next larger key" or "list all keys in [a, b]." Comparison-based tree structures (balanced BSTs, heaps, skip lists) keep keys ordered, enabling range queries, predecessor/successor, and order statistics, at the cost of an extra $\log n$ factor and pointer-chasing overhead. A fourth family, specialized structures (tries, Bloom filters, disjoint-set forests, segment/Fenwick trees), abandons generality entirely to dominate one narrow operation profile.

The decision procedure is a sequence of filtering questions, each of which eliminates whole families of structures. This is not a flowchart to memorize blindly — it is a reconstruction of the reasoning an experienced engineer runs mentally in seconds.

Step 1 — Enumerate required operations. List every operation the workload performs, not just the one that comes to mind first. A "dictionary" that occasionally needs "give me the 10 smallest keys" is not a pure dictionary — it needs order statistics.

Step 2 — Determine required guarantee strength. Decide, per operation, whether average-case, amortized, or hard worst-case bounds are required. Real-time systems, latency-SLA services, and adversarial-input-facing systems (e.g., public web servers) must assume worst case; batch analytics jobs can usually accept amortized or expected bounds.

Step 3 — Check for ordering requirements. If you ever need min/max, predecessor/successor, range queries, or sorted iteration, hash tables are disqualified outright — you need a tree-based or array-based ordered structure.

Step 4 — Check key structure. If keys are strings sharing long common prefixes (URLs, file paths, dictionary words), a trie or radix tree may dominate both hashing and comparison trees by exploiting shared structure instead of paying $O(\log n)$ comparisons or hashing the whole key.

Step 5 — Check concurrency and memory constraints. Balanced BST rebalancing (rotations) is notoriously hard to parallelize correctly; skip lists admit much simpler lock-free concurrent implementations. Cache-conscious systems prefer structures with better locality (arrays, B-trees) over pointer-heavy ones (linked lists, red-black trees) even at equal asymptotic complexity.

Step 6 — Compute expected cost and select. Combine the operation frequencies with the surviving candidates' complexities and pick the minimizer, breaking ties by implementation simplicity and constant factors. ```pseudocode function ChooseStructure(operations, guaranteeLevel, keyType, concurrency, memoryBudget): candidates := { Array, LinkedList, DynamicArray, HashTable, BalancedBST, Heap, SkipList, Trie, BloomFilter }

# Step 3: ordering requirement if RequiresOrderOrRangeQuery(operations): candidates := candidates \ { HashTable, BloomFilter }

# Step 2: worst-case guarantee requirement if guaranteeLevel == WORST_CASE: candidates := candidates \ { HashTable } # expected O(1), not worst-case

# (unless using a worst-case-safe scheme, e.g. cuckoo hashing / dynamic perfect hashing)

# Step 4: key structure exploitation if keyType == STRING_WITH_SHARED_PREFIXES and IsMember(RangeOrPrefixQuery, operations): candidates := candidates ∪ { Trie } # add, don't just filter preferredFamily := Trie

# Step 1: single dominant operation -> specialize if OnlyOperationsAre(operations, {INSERT, EXTRACT_MIN}): return Heap if OnlyOperationsAre(operations, {SEARCH}) and ApproximateOK(operations): return BloomFilter # only if false positives tolerable

# Step 5: concurrency if concurrency == HIGH and NeedsOrder(operations): candidates := PreferIfPresent(candidates, SkipList)

# Step 6: minimize expected cost over remaining candidates best := argmin_{S in candidates} ExpectedCost(S, operations) return best ``` The pseudocode is deliberately a decision procedure over structures, not an algorithm operating on data — the object being manipulated is the design space itself. Each filtering step corresponds to a hard constraint (worst-case safety, ordering) or a dominant-strategy shortcut (single-operation specialization), and the final step is the soft optimization once hard constraints have pruned the space.

The table below is the reference every step of the decision procedure ultimately consults. All logarithms are base 2; $n$ is the number of elements currently stored.

$^\dagger$ assumes a pointer/handle to the node is already held; deletion by key value still costs $O(n)$ to locate it.

Why hash tables are only expected-case, not worst-case. With open addressing (or chaining), a hash function $h$ maps keys from a universe $U$ into $\{0, \dots, m-1\}$. For any fixed $h$, an adversary who knows $h$ can choose $n$ keys that all collide, forcing $\Theta(n)$ probes on every operation — this is the basis of algorithmic-complexity-attack denial of service. Average-case $O(1)$ is provable under simple uniform hashing (each key equally likely to hash anywhere) or via universal hashing, where $h$ is drawn randomly from a family $\mathcal{H}$ such that $\Pr_{h \in \mathcal{H}}[h(x) = h(y)] \le 1/m$ for $x \ne y$. Under universal hashing, the expected chain length (or expected probe count under open addressing with load factor $\alpha = n/m$) is $O(1 + \alpha)$, giving expected $O(1)$ when $\alpha = O(1)$ — but the worst case over all inputs remains $\Theta(n)$, only now the adversary must guess the random seed rather than the fixed function.

Why balanced BSTs give worst-case $O(\log n)$. A red-black tree maintains the invariant that every root-to-leaf path has the same number of black nodes, and no red node has a red child, which together force the longest path to be at most twice the shortest, so height $h = O(\log n)$. Rotation and recoloring after insert/delete restore this invariant in $O(1)$ amortized rotations and $O(\log n)$ recolorings, all along the search path — giving $O(\log n)$ worst case for every dictionary operation, with no dependence on key distribution or adversarial input, unlike hashing.

Why heaps beat balanced BSTs for pure priority-queue workloads. A binary heap is an implicit, array-packed complete binary tree, needing no parent/child pointers (child of index $i$ is at $2i{+}1, 2i{+}2$), so it has better cache locality and lower constant factors than a pointer-based red-black tree, while both give $O(\log n)$ insert/extract-min. The heap sacrifices $O(\log n)$ arbitrary search (finding an arbitrary key requires $O(n)$, since sibling subtrees have no ordering relation to each other) — a fine trade if the workload never searches for arbitrary keys, only ever asks for the current minimum.

Why tries win on shared-prefix key sets. A trie's cost depends on key length $L$, not on the total number of stored keys $n$, because each character selects a child pointer directly rather than requiring a comparison against other stored keys. When $L \ll \log n$ (short fixed-width keys among a huge key set — IP prefixes, DNA k-mers), tries strictly dominate comparison-based trees; when keys are long and mostly unique, the $O(n \cdot L)$ worst-case space cost (unless compressed via a radix tree / Patricia trie) can lose to a hash table.

The honest tradeoff summary. There is a strict impossibility here, not just a folklore rule: a comparison-based structure cannot support search in better than $\Omega(\log n)$ worst case, because a decision tree distinguishing $n$ outcomes needs depth $\ge \log_2 n$. Hashing escapes this bound only by giving up determinism and giving up order — you cannot have expected-$O(1)$ search and worst-case-$O(\log n)$ search and sorted iteration in one structure; every real system's choice is a projection onto two of these three axes.

Consider designing the backend for an autocomplete/typeahead service: given a prefix typed so far, return the 10 most popular completions, and support insertion of new terms with frequency updates, at production request-latency SLAs (worst-case bounded per request).

Step 1 (enumerate operations). `prefixSearch(p) → top-10 by frequency`, `insert/update(term, freq)`, no arbitrary-order iteration needed, no full-range scan.

Step 2 (guarantee level). Latency SLA ⇒ we cannot tolerate a hash table's rare $\Theta(n)$ worst case on a hot path; but we also cannot afford $O(n)$ scans per keystroke at scale.

Step 3 (ordering). Not a total order over all keys — but a prefix structure, which disqualifies hash tables and plain balanced BSTs outright, since neither exploits shared prefixes; both would need an $O(\log n)$ or $O(1)$ search per exact key, but a full range scan of "everything starting with p" in a BST costs $O(\log n + k)$ only if we can identify the subtree efficiently, which a BST keyed on whole strings can do lexicographically — a workable but not optimal fit.

Step 4 (key structure). Terms share long common prefixes by construction — this is exactly the trie's specialty. Decision: use a trie, augmenting each node with a small auxiliary max-heap (or a cached top-10 list) of the best-scoring completions in its subtree, updated incrementally on insert. Trace on a tiny dictionary with typed prefix `"ca"`:

Trie structure (only the relevant subtree shown): root → `c` → `a` → {`t`(120), `r`(95), `b`(40), `p`(15)}; and root → `d` → `o` → `g`(200). 1. Walk root → `c` → `a`: $O(L)$ where $L = 2$, independent of $n = 5$ or $n = 5{,}000{,}000$. 2. At the node for prefix `"ca"`, read the pre-aggregated top-$k$ list stored at that node (maintained by a small bounded max-heap of size 10, updated in $O(\log 10) = O(1)$ per insertion that touches this node). 3. Return `[cat:120, car:95, cab:40, cap:15]` — sorted, in $O(k \log k)$ or already sorted if the auxiliary structure keeps it sorted. Total query cost: $O(L + k \log k)$, completely independent of dictionary size $n$ — exactly the guarantee the SLA needs, and something no plain hash table or balanced BST offers directly, because both would require either scanning all $n$ keys with a prefix test (hash table has no locality among keys sharing a prefix) or walking a lexicographic BST range that could touch $\Omega(n)$ irrelevant nodes if the prefix is short and popular. Insertion of a new term costs $O(L)$ trie-node creations/updates plus $O(\log 10)$ per ancestor node for the auxiliary heap update — still independent of $n$. Contrast with the "obvious" first guess of a hash table on full terms plus a linear scan filtered by prefix: correct results, but $O(n)$ per query — a service with a million terms would do a million string-prefix comparisons per keystroke, violating the latency SLA the moment the dictionary grows past a few thousand entries. The framework's Step 4 filter (shared-prefix key structure) is precisely what catches this before it becomes a production incident.

The decision framework itself synthesizes results developed across three overlapping traditions: balanced search trees, hashing theory, and heap-based priority queues.

Database engines choose B-trees (a wide-fanout generalization of balanced BSTs) for on-disk indexes because they minimize the number of disk-block reads for range queries — exactly the "ordering requirement" filter in Step 3, weighted by an I/O-cost model rather than a comparison-cost model. In-memory caches such as Redis or Memcached lean on hash tables for O(1) key-value lookup, but layer an LRU/LFU eviction structure (often a linked list plus hash table, or an approximate structure) on top precisely because the pure hash table cannot answer "which item is least recently used" — a second operation profile requiring a second structure. Network routers perform longest-prefix matching using tries (specifically Patricia tries or multi-bit tries) because IP prefixes are exactly the shared-prefix key structure Step 4 identifies. Operating system schedulers use heaps or heap-like structures (e.g., the Completely Fair Scheduler's red-black tree in Linux, chosen for its ordering and worst-case bounds together, since scheduling needs both "who runs next" and "insert a newly-woken task") to pick the next runnable task in logarithmic time. Compilers and interpreters use hash tables for symbol tables where insertion order and range queries are irrelevant, and disjoint-set forests for register allocation and type-inference union-find problems where the operation profile is exclusively union/find, not covered by any of the general families above. Every one of these is the same underlying exercise: enumerate operations, filter by guarantee strength and ordering needs, and let the residual structure fall out of the workload rather than out of habit.

Ask the tutor: How would this decision framework change if the workload were mostly writes streamed once and read many times later (a write-once, read-many analytics log)?