% data-structures.tex — the core structures by MECHANISM: memory layout, the
% invariant each keeps, what it costs, and how Swift (stdlib + swift-collections)
% maps onto them. Source: docs/memos/cs-data-structures.md (checked against
% docs/school/notes/knowledge-gaps-2026-09-23.md). Designs built FROM these
% (LRU, rate limiter, ring buffer …): cs/designing-data-structures.tex.
% Hash tables in depth: cs/hashing-deep.tex. Patterns: interview/algorithm-patterns.tex.
% Build ONLY with: tools/print/print-sheet.py <this>.tex --dry-run
% @source: hiot monorepo, docs/school/sheets/cs/data-structures.tex — the SOURCE OF TRUTH; a copy anywhere else (e.g. artur.gurgul.pro) is regenerated from it, never edited
% @labels: area=cs kind=concept level=core platform=general new=no round=missing-2026-09-25 topic=algorithms,data,performance
% @tags: big-o, dynamic-array, amortised-complexity, linked-list, hash-table, open-addressing, binary-heap, red-black-tree, trie, adjacency-list, union-find, swift-collections
\documentclass[8pt]{extarticle}
\usepackage{printup-sheet}
\usepackage{array}

\lstdefinelanguage{SwiftSheet}{
  morekeywords={protocol,class,final,struct,enum,func,var,let,weak,unowned,init,
    if,else,return,guard,self,nil,try,await,async,throws,private,some,mutating,
    true,false,AnyObject,Void,String,Bool,Int,while,for,in,deinit},
  sensitive=true, morecomment=[l]{//}, morecomment=[s]{/*}{*/}, morestring=[b]"}
\lstset{basicstyle=\ttfamily\scriptsize, aboveskip=2pt, belowskip=2pt}

\newcommand\ct[1]{\texttt{#1}}
\tikzset{
  c/.style={cell, minimum width=4.6mm, minimum height=4.2mm, font=\ttfamily\tiny},
  hd/.style={font=\bfseries\small, text=sheetBlue, anchor=west},
  l/.style={font=\tiny, text=black!75, align=center, inner sep=1pt},
  nd/.style={circle, draw=sheetBlue, fill=sheetBlue!8, thick, inner sep=0pt,
             minimum size=4.2mm, font=\ttfamily\tiny},
}

\begin{document}

\sheettitle{Data structures — layout, invariant, cost}{cs · memo}

\oneliner{Every structure is a \textbf{memory layout} plus an \textbf{invariant}
that makes some operations cheap and others expensive. Pick by the operation
that must be fast, then check the constants: \textbf{contiguous memory +
cache lines} beat pointer chasing at equal big-O on every modern CPU.}

\vspace{2pt}
\noindent\begin{tikzpicture}[sheet]
  % ===== dynamic array growth
  \node[hd] at (-0.1,1.95) {Array: append past capacity};
  \foreach \v [count=\i] in {a,b,c,d} \node[c, fill=sheetBlue!10] at (0.2+0.46*\i,1.3) {\v};
  \node[l, anchor=west] at (2.3,1.3) {cap 4, full};
  \foreach \v [count=\i] in {a,b,c,d} \node[c, fill=sheetBlue!10] at (0.2+0.46*\i,0.35) {\v};
  \node[c, fill=sheetOrange!20] at (2.5,0.35) {e};
  \foreach \i in {6,7,8} \node[c] at (0.2+0.46*\i,0.35) {};
  \draw[hot] (1.35,1.07) -- node[l, right]{alloc 2$\times$ + copy $n$ = O(n) once} (1.35,0.58);
  \node[l, align=left, anchor=west] at (0.2,-0.3) {$1{+}2{+}4{+}\dots{+}n < 2n$ copies over $n$ appends\\⇒ \textbf{amortised O(1)}; \ct{reserveCapacity} skips it};
  \draw[sheetGrey!50] (3.95,2.15) -- (3.95,-0.75);
  % ===== linked list scattered in memory
  \node[hd] at (4.0,1.95) {Linked list: pointer chasing};
  \node[c, minimum width=7mm, fill=sheetGreen!10] (n1) at (4.55,1.25) {3|$\bullet$};
  \node[c, minimum width=7mm, fill=sheetGreen!10] (n2) at (6.9,0.75) {7|$\bullet$};
  \node[c, minimum width=7mm, fill=sheetGreen!10] (n3) at (5.1,0.05) {9|/};
  \node[l] at (4.55,1.6) {0x7f10};  \node[l] at (6.9,1.1) {0x2a80}; \node[l] at (5.1,-0.3) {0x9c40};
  \draw[hot, sheetRed] (n1.east) to[bend left=10] (n2.north west);
  \draw[hot, sheetRed] (n2.south west) to[bend left=10] (n3.east);
  \node[l, text=sheetRed, align=left, anchor=west] at (5.6,-0.3) {each hop = likely\\cache miss ($\sim$100 ns)};
  \node[l, align=left, anchor=west] at (4.0,-0.62) {O(1) splice \emph{only if you hold the node}};
  \draw[sheetGrey!50] (7.85,2.15) -- (7.85,-0.75);
  % ===== hash table, open addressing
  \node[hd] at (7.9,1.95) {Hash table: open addressing};
  \foreach \i/\v/\f in {0/{}/white,1/{}/white,2/k1/sheetBlue!12,3/k2/sheetOrange!18,4/\,$\dagger$\,/black!12,5/k3/sheetBlue!12,6/{}/white,7/{}/white}
    \node[c, fill=\f] (h\i) at (8.3+0.48*\i,0.8) {\v};
  \foreach \i in {0,...,7} \node[l] at (8.3+0.48*\i,0.45) {\i};
  \draw[hot] (8.9,1.5) node[l, above]{h(k1)=2} -- (h2.north);
  \draw[hot] (10.1,1.5) node[l, above]{h(k2)=2} to[out=-90,in=90] (h3.north);
  \draw[->, thin, sheetOrange] (h2.south) to[bend right=50] (h3.south);
  \node[l, align=left, anchor=west] at (7.9,0.0) {collision → probe next slot (Swift: linear);\\$\dagger$ = tombstone: a deleted slot must not\\stop later probes · resize at load $\alpha$ = 0.75};
  \draw[sheetGrey!50] (12.15,2.15) -- (12.15,-0.75);
  % ===== binary heap: tree + array
  \node[hd] at (12.2,1.95) {Min-heap = complete tree in array};
  \node[nd] (r) at (13.6,1.45) {1};
  \node[nd] (a) at (12.95,0.95) {3}; \node[nd] (b) at (14.25,0.95) {2};
  \node[nd] (a1) at (12.6,0.45) {7}; \node[nd] (a2) at (13.3,0.45) {4};
  \node[nd] (b1) at (13.9,0.45) {5};
  \draw (r)--(a) (r)--(b) (a)--(a1) (a)--(a2) (b)--(b1);
  \foreach \v [count=\i from 0] in {1,3,2,7,4,5} {\node[c, minimum width=4mm, fill=sheetBlue!10] (y\i) at (12.55+0.4*\i,-0.2) {\v}; \node[l] at (12.55+0.4*\i,-0.48) {\i};}
  \draw[->, thin, sheetOrange] (y1.north) to[bend left=60] node[l, above, pos=0.5]{} (y3.north);
  \draw[->, thin, sheetOrange] (y1.north) to[bend left=60] (y4.north);
  \node[l, align=left, anchor=west] at (14.75,0.9) {children of $i$:\\$2i{+}1$, $2i{+}2$\\parent: $(i{-}1)/2$};
  \node[l, align=left, anchor=west] at (14.9,0.25) {no pointers,\\no gaps};
\end{tikzpicture}

\begin{multicols}{2}
\footnotesize\setstretch{1.0}

\section{How each one works}
\begin{itemize}
  \item \textbf{Array} — one contiguous block: \ct{base + i·stride} ⇒ O(1) index.
        Sequential scans ride the hardware \textbf{prefetcher}; a cache line
        (64\,B x86, 128\,B Apple silicon) brings 8–16 \ct{Int}s per miss.
        Insert/delete in the middle shifts O(n). Swift grows geometrically (2$\times$).
  \item \textbf{Linked list} — one heap allocation per node + next (and prev)
        pointers. Wins only for O(1) splice at a \emph{held} node (LRU, free lists)
        and stable node addresses. Finding the node is O(n).
  \item \textbf{Stack} LIFO (calls, DFS, undo) · \textbf{queue} FIFO (BFS,
        scheduling) · \textbf{deque} both ends O(1) (sliding window, work
        stealing). Array queue with \ct{removeFirst()} is O(n) per dequeue → ring
        buffer (head index) or two stacks.
  \item \textbf{Hash table} — \ct{hash(key) mod m} → bucket. Load
        $\alpha = n/m$. \textbf{Chaining}: bucket = list/tree, tolerates
        $\alpha>1$, pointer-heavy. \textbf{Open addressing}: entries inline,
        probe on collision (linear/quadratic/double), cache-friendly, needs
        $\alpha<1$ and tombstones. Resize = rehash every entry, O(n) once.
  \item \textbf{BST} — left $<$ node $<$ right; all ops O(h). Sorted inserts make
        a list: h = n. \textbf{AVL}: subtree heights differ $\le$1, h $\le$
        1.44\,log n → faster reads, more rotations. \textbf{Red-black}: no red–red,
        equal black height, h $\le$ 2\,log(n+1), $\le$2 rotations per insert, $\le$3
        per delete → cheaper writes (\ct{std::map}, Java \ct{TreeMap}).
        Disk/DB: \textbf{B-tree}, fan-out $\sim$100s, one node = one page.
  \item \textbf{Binary heap} — complete tree in an array, parent $\le$ children.
        peek O(1), push = append + sift-up O(log n), pop = move last to root +
        sift-down O(log n), \textbf{heapify O(n)}. Priority queues, Dijkstra, top-k.
  \item \textbf{Trie} — node per prefix, children by character, \ct{isEnd} flag.
        O(L) per op, independent of key count; prefix queries a hash set can't do.
  \item \textbf{Graph} — adjacency \textbf{list} O(V+E) space, neighbours in
        O(deg): sparse graphs (almost all). \textbf{Matrix} V$\times$V bits/weights,
        O(1) ``edge u–v?'': dense graphs, Floyd–Warshall.
  \item \textbf{Union-find} — parent array + path compression + union by rank
        → O($\alpha$(n)) $\approx$ O(1): components, Kruskal.
\end{itemize}

\section{Example — a queue that is really O(1)}
\begin{lstlisting}[language=SwiftSheet]
struct Queue<T> {               // amortised O(1), no Deque needed
  private var items: [T?] = []; private var head = 0
  mutating func enqueue(_ x: T) { items.append(x) }
  mutating func dequeue() -> T? {
    guard head < items.count, let x = items[head] else { return nil }
    items[head] = nil; head += 1           // O(1): no shifting
    if head > 64 && head * 2 > items.count {   // compact now and then
      items.removeFirst(head); head = 0 }
    return x }
}
\end{lstlisting}

\section{Picture — one graph, two layouts}
\begin{tikzpicture}[sheet]
  \node[nd] (A) at (0,1.1) {A}; \node[nd] (B) at (1.1,1.1) {B};
  \node[nd] (C) at (0,0) {C};   \node[nd] (D) at (1.1,0) {D};
  \draw[thick] (A)--(B) (A)--(C) (B)--(D) (C)--(D);
  \node[l, text=sheetBrown] at (0.55,-0.45) {V=4, E=4};
  % adjacency list
  \node[hd, font=\bfseries\scriptsize] at (1.7,1.45) {list: V + 2E cells};
  \foreach \k/\n [count=\i] in {A/{B C},B/{A D},C/{A D},D/{B C}} {
    \node[c, fill=sheetBlue!12] (k\i) at (2.0,1.35-0.38*\i) {\k};
    \node[c, anchor=west, minimum width=9mm, fill=sheetGreen!8] at (2.4,1.35-0.38*\i) {\n};
    \draw[->, thin] (k\i.east) -- ++(0.17,0); }
  % matrix
  \node[hd, font=\bfseries\scriptsize] at (4.05,1.45) {matrix: V\textsuperscript{2} cells};
  \foreach \r/\row [count=\i] in {A/{0,1,1,0},B/{1,0,0,1},C/{1,0,0,1},D/{0,1,1,0}} {
    \node[l] at (4.2,1.35-0.38*\i) {\r};
    \foreach \v [count=\j] in \row {
      \ifnum\v=1 \node[c, minimum width=3.8mm, minimum height=3.8mm, fill=sheetOrange!20] at (4.2+0.38*\j,1.35-0.38*\i) {1};
      \else \node[c, minimum width=3.8mm, minimum height=3.8mm] at (4.2+0.38*\j,1.35-0.38*\i) {0}; \fi } }
  \node[l, align=left, anchor=west] at (6.2,0.7) {1M users,\\$\sim$200 friends:\\list $\approx$ 2$\times$10\textsuperscript{8}\\matrix 10\textsuperscript{12}};
\end{tikzpicture}

\columnbreak

\section{Big-O — average (worst)}
{\scriptsize
\begin{tabular}{@{}>{\raggedright\arraybackslash}p{15mm}>{\raggedright\arraybackslash}p{9mm}>{\raggedright\arraybackslash}p{11mm}>{\raggedright\arraybackslash}p{13mm}>{\raggedright\arraybackslash}p{19mm}@{}}
\toprule
\textbf{structure} & \textbf{access} & \textbf{search} & \textbf{insert / delete} & \textbf{note}\\
\midrule
array & 1 & n & n; end: 1\textsuperscript{am} & sorted: search log n\\
linked list & n & n & 1 at node & find the node: n\\
stack/queue/deque & ends 1 & n & ends 1 & array queue front: n\\
hash table & — & 1 (n) & 1\textsuperscript{am} (n) & hashing key = O(len)\\
BST, plain & — & log n (n) & log n (n) & sorted input → n\\
AVL / red-black & — & log n & log n & in-order = sorted\\
binary heap & min 1 & n & log n & build O(n)\\
trie & — & L & L & L = key length\\
adj. list / matrix & — & deg / 1 & 1 / 1 & space V+E / V\textsuperscript{2}\\
\bottomrule
\end{tabular}}

\section{Swift mapping}
{\scriptsize
\begin{tabular}{@{}>{\raggedright\arraybackslash}p{21mm}>{\raggedright\arraybackslash}p{48mm}@{}}
\toprule
\ct{Array} & dynamic array, value type + copy-on-write; \ct{ContiguousArray} skips NSArray bridging\\
\ct{Set} / \ct{Dictionary} & hash tables, open addressing with linear probing, max load 3/4; order \textbf{unspecified}\\
\ct{Deque} & swift-collections: ring buffer, O(1) both ends\\
\ct{Heap} & swift-collections: \textbf{min-max} heap — \ct{min}/\ct{max} O(1), \ct{popMin}/\ct{popMax} O(log n)\\
\ct{OrderedSet} / \ct{OrderedDictionary} & array + hash index: O(1) lookup, insertion order kept, \textbf{remove from middle O(n)}\\
\ct{TreeSet} / \ct{TreeDictionary} & persistent hash tries (CHAMP) — \emph{not} sorted trees\\
sorted tree, list & \textbf{none built in}: sorted array + binary search, or write one\\
\bottomrule
\end{tabular}}

\section{Interview traps}
\begin{itemize}
  \trap{``Linked lists insert faster'' — only once you hold the node; the O(n)
        walk and cache misses usually lose to \ct{Array}'s memmove.}
  \trap{Hash O(1) is \emph{average, amortised}: O(n) on collisions/flooding, one
        insert can rehash O(n), and hashing a long string is O(length).}
  \trap{A heap is not sorted: no binary search, in-order isn't ordered,
        ``contains'' is O(n).}
  \trap{\ct{Dictionary} order and \ct{hashValue} change per launch (seeded
        hasher) — never persist them or assert on them in a test.}
  \trap{Swift class list: a 1M-node chain frees \emph{recursively} on
        \ct{deinit} → stack overflow; unlink iteratively. Make \ct{prev}
        \ct{weak}/\ct{unowned} or a doubly linked list is a retain cycle.}
  \trap{Amortised $\neq$ worst case: a resize inside a 16\,ms frame or audio
        callback still hitches — pre-size or use a fixed ring buffer.}
  \trap{\ct{String} is not \ct{Int}-indexable (grapheme clusters) —
        \ct{Array(s)} once if you need random access.}
\end{itemize}

\section{Remember}
\textbf{Layout decides speed, invariant decides big-O.} Contiguous by default;
pointers only when you must splice.

\section{Likely questions}
\begin{enumerate}
  \item Why is append amortised O(1)? — doubling: total copies $<2n$.
  \item Chaining vs open addressing? — pointers \& $\alpha>1$ vs inline \& probing.
  \item AVL or red-black? — reads vs writes; RB rotates less.
  \item Heapify cost? — O(n): most nodes are near the leaves.
  \item Sparse graph storage? — adjacency list, O(V+E).
  \item Ordered map in Swift? — none built in: sorted keys + binary search, or a tree.
  \item Why is a DB index a B-tree, not a BST? — fan-out: few page reads per lookup.
\end{enumerate}

\end{multicols}

\noindent{\footnotesize\color{sheetGrey}\textit{Related:} designing-data-structures
(LRU, ring buffer) · hashing-deep · algorithm-patterns · strings-and-collections ·
value-vs-reference (COW)}

\end{document}