Choosing data structures — arrays, lists, stacks, hashes, and trees
Data structures don't have superior and inferior. There are only design differences in which operations were sped up, and which were sacrificed.
Arrays give fast index access but slow inserts in the middle. Linked lists are the reverse. Once that symmetry is visible, the criteria for choosing become clear.
What you'll learn in this chapter
- Which operation each major data structure speeds up, and which it sacrifices
- The difference in retrieval order between stacks and queues
- How hash maps average
O(1), and what the worst case looks like - What trees and tries are each for
Uses big-O from Complexity.
Complexity per operation
Line up the major structures. n is the number of elements.
| Index access | Lookup | Insert at head | Insert at tail | Insert / delete in middle | |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(1) amortized | O(n) |
| Linked list | O(n) | O(n) | O(1) | O(1) | O(1) ※ |
| Hash map | — | O(1) avg | — | O(1) avg | O(1) avg |
| Balanced BST | — | O(log n) | — | O(log n) | O(log n) |
※ Linked list "insert / delete in middle" is O(1) only when you already hold the node one before that position. A node only holds a reference to the next one, so the node you rewire is the one before. Starting from having to find the position adds the O(n) lookup. "Insert at tail" is likewise O(1) only when the list holds a reference to the tail node; with only a reference to the head, walking to the tail adds O(n).
The array's O(1) for "insert at tail" is an amortized value. The assumption here is a growable array (dynamic array): when the capacity runs out it reallocates and copies every element, so that one round costs O(n). Averaged out, each insert is O(1).
Array — laid out in a contiguous region
Elements sit contiguously in memory. So any element is reachable with just "head address + index × element size". That's the substance of O(1) index access.
In exchange, inserting or deleting in the middle requires shifting every element after it. Inserting at the head moves everything, so it's O(n).
Contiguity has another benefit. Adjacent elements share cache lines, so processes that walk sequentially get measurably faster. Even at the same O(n), walking an array is normally faster than walking a linked list.
Linked list — nodes point to the next
Each element (node) holds a value and a "reference to the next node". They don't need to be contiguous in memory.
Inserting and deleting is just rewiring three references, so if you know the position, it's O(1). Nothing has to shift.
In exchange, getting to "the 5th element" means walking five hops from the head, so index access is O(n). Because of this, binary search doesn't work on linked lists — you can't jump to the middle.
Linked lists shine when you hold the position and insert/delete frequently. A typical case is an LRU cache combining a hash map with a linked list: the hash map holds references to the nodes, and list rewiring is done in O(1). But with only a next reference, holding a node isn't enough to reconnect what came before it. Rewiring in O(1) needs to reach the node one before — either give nodes a reference to the previous one, or arrange the hash map so it yields that node.
Stack and queue — different retrieval order
These two differ only in "where you put in and where you take out".
| Put in | Take out | Order | |
|---|---|---|---|
| Stack | Tail | Tail | LIFO (Last In, First Out) |
| Queue | Tail | Head | FIFO (First In, First Out) |
Stack is LIFO; queue is FIFO. Remember the pairing the wrong way and you'll pick the wrong one in practice.
Recognizing by use case is more reliable.
| Where they're used | |
|---|---|
| Stack | Function call history (call stack), undo, bracket matching, depth-first search |
| Queue | Print spooler, job queues, incoming requests, breadth-first search |
"Undo" returns from the most recent step, so it's a stack. "Waiting in line" goes in order of arrival, so it's a queue. Both come up in Graphs and traversal as building blocks that decide traversal order.
Hash map — compute the location from the key
Pass the key through a hash function to a number, and use that to decide a position in an internal array.
Lookup does the same computation. No scan, so it averages O(1). This is where people misunderstand: it's not "fast because it scans an array efficiently". It's fast because it doesn't scan.
Worst case is O(n)
Different keys can hash to the same index (a collision). Colliding entries are kept together — commonly in a chain — and lookup walks that group.
If every key collides on the same index, the chain becomes one line of n entries, and lookup degrades to O(n). In practice, a good hash function and appropriate sizing avoid this — but the guarantee is on the average, not the worst case.
That worst case is why hash-flooding attacks — deliberately sending many colliding keys to stall a server — are possible. Language runtimes mix a random seed into their hash functions as a countermeasure.
No ordering
Hash maps don't preserve insertion order or key order. If you need "iterate in key order" or "iterate a range", a tree is better suited.
Trees — preserving hierarchy and order
A binary search tree maintains the invariant that "every node in the left subtree is smaller than me, and every node in the right subtree is larger" at every node. A subtree is a child and everything hanging below it. So a lookup can discard one branch each round, giving O(log n). It's the same idea as binary search, realized by connecting nodes instead of on an array.
But performance drops when it becomes skewed. Inserting sorted data in order keeps extending to the right, effectively becoming a linked list — degrading to O(n). To prevent this, balanced binary search trees (red-black tree, AVL tree) reshape themselves on insert and delete.
The B-Tree used in database indexes is also a tree with the same "discard one branch each round" idea. Its design packs many keys per node to reduce disk reads.
Trie — specialized for string prefix matching
A trie is a tree where each edge corresponds to one character of a string.
Storing cat / car / card collapses their shared prefix ca into a single path.
With this structure, "enumerate every word beginning with ca" is just descending to the ca node and walking its subtree. Descending to the ca node costs the length of the search string, independent of the dictionary's total word count. From there, you walk only as many nodes as there are matches.
Uses involve prefix matching.
- Autocomplete in search boxes
- Dictionary headword lookup
- IP address routing tables (longest match)
- Input completion, spell checking
What tries handle is prefixes of strings. Shortest-path problems on graphs are covered by Graphs and traversal, and if edges have weights, a different algorithm like Dijkstra's is needed. The word "tree" is shared, so they can look like the same topic, but the problems being solved differ.
Choosing criteria
| Want to | Suited structure |
|---|---|
| Fetch fast by index | Array |
| Walk everything in order | Array (fits in cache) |
| Frequently insert / delete in the middle | Linked list |
| Look up fast by key | Hash map |
| Need key order or range | Balanced BST |
| Process LIFO | Stack |
| Process FIFO | Queue |
| Look up by string prefix | Trie |
Common misconceptions
"Stack is FIFO." — Stack is LIFO. FIFO is queue.
"Hash maps are fast because of clever searching." — They're fast because they don't search. The position is computed from the key. The moment you step through elements one by one, you're at O(n).
"Hash maps are always O(1)." — Average is O(1). Concentrated collisions make it O(n) in the worst case.
"Linked list is a strictly better array." — Index access becomes O(n), and cache efficiency drops. It only wins when inserts and deletes are frequent.
"BST is always O(log n)." — Skew degrades it to O(n). Guaranteeing the log requires balancing.
Exercises
Q1. Which data structure is appropriate for keeping the browser's back-button history?
Answer and explanation
Answer: Stack
"Back" navigates to the page you just saw. You pop in reverse order of visits, so it's LIFO.
Push a page on each visit; pop the top on "back". If you want "forward", push the popped page onto a separate stack.
A queue (FIFO) would send you back to the first page ever visited.
Q2. From a 1,000,000-word dictionary, enumerate every word beginning with "pro". Which is better: a hash map or a trie?
Answer and explanation
Answer: Trie
Hash maps look up only by exact key. Prefix search means scanning all 1,000,000 entries comparing the first three characters — O(n). The hash doesn't preserve original string order or prefix information, so it doesn't fit.
A trie descends p → r → o — three levels — and everything under that node is "words beginning with pro". Descent cost is decided by the search string length (3), independent of the dictionary's total word count.
That's why tries are used for autocomplete.
Q3. "Repeatedly taking elements from the head of an array" is reported as slow. Cause and countermeasure?
Answer and explanation
Answer: Deleting from the head of an array is O(n), making the whole thing O(n²).
Since an array is contiguous, deleting the head shifts everything else forward by one. That's O(n) per operation and O(n²) over n rounds.
Two countermeasures.
- Use a structure appropriate for a queue — a linked list deletes from the head in
O(1) - Don't delete; advance the read position — hold a variable pointing to the head index and increment it on each take. The array isn't modified, so each operation is
O(1)
The second is the "ring buffer" idea, realizing a queue without physically moving elements. Even when you can't change the data structure, changing how you operate on it can drop the complexity.
Summary
- Data structures differ in "which operations are sped up, which are sacrificed"
- Arrays are
O(1)index access butO(n)middle inserts/deletes. Linked lists are the reverse - Stacks are LIFO; queues are FIFO
- Hash maps average
O(1)because they compute the position from the key rather than scan. Concentrated collisions degrade toO(n) - Hash maps have no order. Use a balanced BST when order or ranges are required
- BSTs degrade to
O(n)when skewed. Balancing keeps them atO(log n) - Tries are structures for string prefix matching and unrelated to route optimization
- Database Design Guide — Introduction to index design — How a B-Tree index speeds up lookup
What to read next
- Bit operations — Holding a set of booleans in a single integer