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.
The same structures in PicoLisp
PicoLisp gives you the main structures with almost no ceremony, which makes it a good place to feel their trade-offs:
# Stack: push and pop on the front of a list, O(1)
(setq S NIL)
(push 'S 1 2 3) # S = (3 2 1)
(pop 'S) # -> 3
# Queue: fifo uses a circular list, O(1) at both ends
(setq Q NIL)
(fifo 'Q 'a 'b 'c)
(fifo 'Q) # -> a
# Balanced binary tree: idx, O(log n) insert and lookup, kept sorted
(setq T1 NIL)
(for W '("vim" "emacs" "pil" "ed") (idx 'T1 W T))
(idx 'T1) # -> ("ed" "emacs" "pil" "vim")
(idx 'T1 "pil") # found: returns the node
# Association list: fine for small maps
(setq Ports '((ssh . 22) (http . 80)))
(cdr (assoc 'ssh Ports)) # -> 22
idx is the one most people miss. It is a self-balancing binary tree built from ordinary cells, and it is what you should reach for when an association list gets long.
Measuring instead of guessing
Big-O tells you how things grow, not how fast they are for your data. Measure:
python3 -m timeit -s "L=list(range(10**6)); S=set(L)" "999999 in L" # list: linear scan
python3 -m timeit -s "L=list(range(10**6)); S=set(L)" "999999 in S" # set: hash lookup
The list membership test takes milliseconds; the set takes tens of nanoseconds, a difference of about five orders of magnitude. In PicoLisp, (bench ...) does the same job at the REPL. Five minutes of measuring beats an hour of arguing about which structure “should” be faster, and it is how you discover that cache-friendly arrays often beat theoretically better linked structures for small sizes.