Lists §

How it works. An array is a block of $n \times w$ bytes (where $w$ is the element width) allocated contiguously. Element $i$ lives at address $\text{base} + i \cdot w$, so the CPU computes the address with a single multiply-and-add. No pointer chasing is needed.

Worked example. Consider an array of 8 int32 values (4 bytes each) starting at address 0x1000:

Accessing index 5: address = 0x1000 + 5 × 4 = 0x1014 → value 3. One memory access, $O(1)$.

Cache locality. A cache line (typically 64 bytes) loads 16 int32 elements at once. Sequential iteration over an array achieves near-peak bandwidth because each access hits the same cache line. This is why arrays outperform linked lists for iteration despite $O(n)$ insertion. See Memory Hierarchy for the full treatment of cache lines, spatial and temporal locality, and the memory wall.

Lookup tables. A precomputed array indexed by the key itself (e.g., a 256-entry table for byte values). $O(1)$ access, $O(|K|)$ space. Used for character classification, base64 decoding, and small integer key maps. See Knuth, TAOCP Vol. 1: Fundamental Algorithms for the classical treatment of arrays and sequential access.

Example problem.

How it works. A vector maintains two numbers: size (number of elements) and capacity (number of allocated slots). When size == capacity, the vector allocates a new block of $c \times \text{capacity}$ bytes, copies all elements, and frees the old block. The amortized cost per insertion is $\frac{1}{1 - 1/c}$ element-copies.

Growth factor. Any constant factor $c > 1$ gives $O(1)$ amortized per insertion. For example, $c = 1.5$ gives amortized cost 3 per insertion; $c = 2$ gives amortized cost 2. The factor $c = 2$ minimizes the number of reallocations ($\log_2 n$), while smaller factors reduce peak memory waste. Peak memory usage is at most $c \cdot n$ elements (just before a shrink, if supported).

Worked example. Start with capacity 1, growth factor 2:

Total copies for 9 insertions: 1+2+4+8 = 15 < 2×9. Amortized ≈ 1.67 per insertion.

Language implementations. In C++, std::vector uses geometric growth (typically doubling). In Rust, Vec uses a similar strategy. In Python, list over-allocates by $\sim 12.5\%$ per growth step for large lists; for small lists the capacity roughly doubles. See CLRS, Ch. 10 (Elementary Data Structures) for the amortized-analysis treatment of dynamic arrays.

Vectors and sorting. A sorted vector supports $O(\log n)$ binary search.

Example problem.

How it works. Each node is a separate heap allocation containing the element and one or two pointers. To insert after node $p$, allocate a new node, set its next to $p.\text{next}$, then set $p.\text{next}$ to the new node. No existing elements move.

Worked example. Insert 42 after the node holding 7 in the list 3 → 7 → 99:

1. Allocate new node: new = Node(42, next = NULL)
2. new.next = 7.next → new.next points to node(99)
3. 7.next = new → node(7).next now points to node(42)

Result: 3 → 7 → 42 → 99. Three pointer writes, $O(1)$.

Cache locality. Each node is a separate heap allocation, so iteration causes a cache miss per node (unless the allocator happens to place them adjacently). This is the fundamental trade-off: linked lists buy $O(1)$ splice at the cost of spatial locality. They are preferred when:

• Frequent insertion/deletion at arbitrary positions (e.g., an editor’s undo buffer).
• The collection is small and the pointer overhead is negligible.
• A memory pool or arena allocator is used to improve locality.

In practice, most general-purpose containers (Java ArrayList, C++ std::vector) prefer arrays over linked lists. See Memory Management for the heap allocation model that makes linked lists expensive, and CLRS, Ch. 10 (Elementary Data Structures) for the pointer-relinking analysis.

Example problem.

Stack (LIFO). The most recent element is the first removed. Implementations: an array with a top index (push = write at top, pop = read and decrement), or a singly linked list where the head is the top. Typical uses: call-stack management, expression evaluation, DFS traversal (see Graphs), undo/redo buffers.

Worked example (stack). Push 3, 7, 1; pop; push 9; pop:

Queue (FIFO). The oldest element is the first removed. Implementations: a circular buffer (array with head and tail indices that wrap around), or two stacks (enqueue on one, dequeue from the other, amortized $O(1)$). Typical uses: BFS traversal (see Graphs), task scheduling, I/O buffering, message passing.

Worked example (queue, circular buffer of size 4).

Deque (double-ended queue). Supports push/pop at both ends in $O(1)$. Implementations: a circular buffer with room for one extra slot (to distinguish full from empty), or a block list (array of fixed-size blocks, each pointing to the next/previous block). Typical uses: sliding-window maximum, BFS with backtracking, undo with both directions.

Relationship to other structures. A stack is a vector with only push_back/pop_back exposed. A queue is a vector (or circular buffer) with push_back/pop_front. A deque is a vector with both ends exposed. The restriction is purely on the interface, not the implementation. See CLRS, Ch. 10 (Elementary Data Structures) for the standard stack/queue/deque definitions.

Example problem.

How it works. Each element is hashed $k$ times, producing $k$ bit positions in the array. Insertion sets those bits. A query checks whether all $k$ positions are set. As more elements are inserted, bits collide and the false-positive rate rises.

Worked example. Bit array of $m = 16$ bits, $k = 3$ hash functions. Insert elements A, B, C:

Array after inserts: [0,0,1,0,1,0,0,1,0,1,0,1,0,1,0,0]

Query D (hashes to positions 2, 7, 14): position 14 is 0 → definitely absent. ✓ Query E (hashes to positions 2, 7, 13): all set → maybe present (false positive if E was never inserted).

Optimal parameters. For $n$ elements and target FPR $\varepsilon$:

For 10M elements at 1% FPR: $m \approx 9.6$ bits per element, total $\approx 96$ million bits $\approx 12$ MB.

Uses. Cache filtering (avoid disk lookups for missing keys), deduplication (web crawlers), distributed systems (Cassandra’s bloom filter on SSTables — see Key-Value Stores), and network packet filtering.

Counting Bloom filters replace bits with small counters (typically 4 bits), enabling deletion at the cost of 4× space.

Authoritative source

• Burton H. Bloom, “Space/Time Trade-offs in Hash Coding with Allowable Errors,” CACM 13(7):422–426, 1970

Example problem.

Problem. You are building a text editor with an undo/redo system. The user can type (push), undo (pop), and redo (re-push). You also need to support “jump to line 500” (random access). Which combination of data structures would you use, and why?