Knowledge base / Computing / Computer science, theory & data
Data Structures and Alogrithms
Here is the truth about data structures and algorithms: a data structure is a bet about which questions you’ll ask most, and an algorithm is how you answer them. Pick the wrong bet and even brilliant code crawls.
What it is, in plain words
This page sits beside Algorithms as a more structure-focused map. The classic cast:
| Structure | Good at | Weak at |
|---|---|---|
| Array / slice | Index access | Insert at front |
| Dynamic array (Vec, list) | Amortised append | Mid inserts |
| Linked list | Splice if you have a pointer | Random access |
| Stack / queue | LIFO / FIFO patterns | Search |
| Hash table | Lookup/insert average | Range queries, ordering |
| BST / tree map | Ordered ops | Cache locality vs hash |
| Heap | Min/max repeatedly | Arbitrary delete |
| Graph (adj list) | Sparse relations | Dense matrix ops |
| Trie | Prefix search | Memory use |
Why it matters
Databases, compilers, games, routers and ML frameworks are data-structure museums. When a feature is slow, the fix is often “wrong structure” rather than “buy a bigger CPU”. See also big-O notes on the Algorithms page.
An everyday analogy: kitchen storage
Spices in a drawer (array) are fine for ten tins. Spices on a lazy Susan labelled by name (hash table) win at fifty. A pantry ordered alphabetically (tree) helps when you want “everything between M and P”. The food didn’t change – the questions did.
A hands-on example
from collections import deque
import heapq
# Stack
st = []
st.append(1); st.append(2); print(st.pop()) # 2
# Queue
q = deque()
q.append("a"); q.append("b"); print(q.popleft()) # a
# Hash map frequency count
freq = {}
for ch in "voidlinux":
freq[ch] = freq.get(ch, 0) + 1
# Min-heap of (priority, item)
h = []
heapq.heappush(h, (2, "write docs"))
heapq.heappush(h, (1, "fix bug"))
print(heapq.heappop(h)) # (1, 'fix bug')
# Graph as adjacency list + BFS
g = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
seen, dq = {"A"}, deque(["A"])
while dq:
u = dq.popleft()
for v in g[u]:
if v not in seen:
seen.add(v); dq.append(v)
print(seen)
Implement each once by hand. Then use your language’s battle-tested versions in production.
Common misconceptions
- “Hash tables are always faster.” Until adversarial keys, memory pressure or ordered traversal shows up.
- “Linked lists are good for inserts.” In practice arrays often win because of caches.
- “I must invent my own.” You must understand them. Inventing a production hash table is a research hobby.
- “Graphs are exotic.” Dependency trees, social links, maps and type hierarchies are graphs.
Studying without drowning
Implement each structure once in a language you like. Then solve a handful of problems that force its use – frequency counting for hash maps, scheduling for heaps, maze/path for graphs. Competitive programming sites are optional gyms; your own tools (a tiny Redis-like toy, a pathfinder for a game) teach the same muscles with more joy.
When reading production code, ask: which structure is this, and which question was it optimised to answer? That habit alone levels up design reviews.
Connections
Algorithms, Computer Science, Stacks.
NumPy – contiguous arrays at scale.
PicoLisp – lists as the native structure.
Picolisp, Picolisp Machine, pil sources