Chapter 7: Data Structures that Shape Algorithms

Algorithms rarely live alone; the data structure you choose will often decide the speed, memory use, and clarity of your solution. This chapter surveys the core structures that most algorithms lean on, explains their strengths and weaknesses, and shows how to implement and combine them in practical code.

Arrays, Lists, and Stacks

Arrays and lists store sequences; stacks specialize that idea for last-in first-out workflows. Many everyday algorithms start by picking one of these and then layering rules about how items are added or removed.

Using contiguous array storage and flexible list growth

An array is a contiguous block of memory that gives O(1) index access; it shines when you know the size in advance or when you need predictable layout. A list (in languages where it means a dynamic array) grows automatically; appends amortize to O(1) since occasional resizes copy elements. Linked lists trade O(1) insertion at known positions for O(n) indexing, which can be ideal when you mostly traverse and splice.

# Dynamic-array style list: O(1) average append, O(1) index
nums = []
nums.append(13)
nums.append(21)
x = nums[1]  # 21

Implementing a stack for LIFO workflows

A stack supports push, pop, and peek. Use it for depth-first search, undo systems, parsing, or any time you backtrack. Typical operations are O(1) on a dynamic array.

class Stack:
  def __init__(self):
    self._a = []
  def push(self, x):
    self._a.append(x)
  def pop(self):
    return self._a.pop()
  def peek(self):
    return self._a[-1] if self._a else None

s = Stack()
s.push("match")
s.push("paren")
top = s.pop()  # "paren"

Comparing access and insertion costs for sequences

The following quick reference helps when choosing a sequence type for core operations; costs refer to big-O time.

Queues, Priority Queues, and Heaps

Queues process items in arrival order; priority queues process highest priority first. Heaps implement priority queues efficiently with a small and elegant invariant.

Building a FIFO queue for breadth-first work

A first-in first-out queue is perfect for breadth-first search, task scheduling, and rate limiting. Use a deque so both ends are O(1).

from collections import deque

q = deque()
q.append("A")        # enqueue
q.append("B")
first = q.popleft()  # dequeue, "A"

Creating a priority queue with a binary heap

A binary heap is a complete binary tree stored in an array where each parent is less than or equal to its children for a min-heap. Push and pop are O(log n); peek is O(1). This makes heaps ideal for Dijkstra, A*, event simulation, and selecting the smallest or largest k items.

import heapq

h = []
heapq.heappush(h, (2, "task-2"))
heapq.heappush(h, (1, "task-1"))
heapq.heappush(h, (3, "task-3"))
prio, item = heapq.heappop(h)  # (1, "task-1")

Maintaining a bounded heap for top-k selection

To keep only the k best items, store the current k in a heap and eject when you exceed k. Use a min-heap for top-k largest by keeping negatives or by comparing key values carefully.

import heapq

def top_k_largest(stream, k):
  h = []
  for x in stream:
    if len(h) < k:
      heapq.heappush(h, x)
    else:
      if x > h[0]:
        heapq.heapreplace(h, x)
  return sorted(h, reverse=True)

Hash Tables and Dictionaries

Hash tables map keys to values using a hash function; average case operations are O(1). Collisions are resolved by strategies such as chaining or open addressing. Dictionaries in many languages are high-performance hash tables with practical features built in.

Using a dict for constant-time lookups and inserts

A dict gives O(1) average insert, get, and delete. Use it for membership tests, frequency counts, and adjacency maps. Keys must be hashable; design keys so that equality implies identical meaning.

counts = {}
for w in ["to", "be", "or", "not", "to", "be"]:
  counts[w] = counts.get(w, 0) + 1
is_present = "or" in counts  # True

Handling collisions and managing load factor

As a table fills, collisions grow more likely. Implementations resize to keep the load factor under a target; this gives stable O(1) performance. In chaining, each bucket holds a small list; in open addressing, probing searches for a nearby slot. Good hashing spreads keys uniformly and avoids patterns.

# Educational sketch of chaining with very small table size
class TinyMap:
  def __init__(self, m=4):
    self.m = m
    self.b = [[] for _ in range(m)]
  def _i(self, k):
    return hash(k) % self.m
  def put(self, k, v):
    i = self._i(k)
    for j, (kk, _) in enumerate(self.b[i]):
      if kk == k:
        self.b[i][j] = (k, v); return
    self.b[i].append((k, v))
  def get(self, k, default=None):
    i = self._i(k)
    for kk, vv in self.b[i]:
      if kk == k:
        return vv
    return default

Designing compound keys and memoization with dict

Compound keys pack multiple fields into a hashable tuple; this is useful for dynamic programming or caching function results. Memoization turns repeated expensive work into fast lookups.

memo = {}
def fib(n):
  if n <= 1:
    return n
  if n in memo:
    return memo[n]
  memo[n] = fib(n - 1) + fib(n - 2)
  return memo[n]

Trees and Balanced Trees

Trees organize data hierarchically; binary search trees give ordered search with structure guarantees when balanced. Balanced trees keep height near log n so operations stay fast regardless of input order.

Searching a binary search tree by following order

In a binary search tree, left child keys are less than the node, and right child keys are greater than the node. Lookups descend by comparisons until a match or a leaf.

class Node:
  def __init__(self, k, v):
    self.k, self.v = k, v
    self.l = None; self.r = None

def bst_get(t, k):
  cur = t
  while cur:
    if k == cur.k:
      return cur.v
    cur = cur.l if k < cur.k else cur.r
  return None

Keeping height small with AVL and red-black balancing

AVL trees rebalance using rotations that maintain a height difference of at most one; searches, inserts, and deletes stay O(log n). Red-black trees enforce color rules that guarantee logarithmic height with fewer rotations on average. Either choice gives predictable ordered performance and efficient range queries.

Storing blocks on disk with B-tree families

B-tree and B+-tree structures group many keys per node to match disk or page size; this reduces I/O and supports very large ordered maps. Databases and filesystems rely on these structures to keep lookups near O(log_b n) where b is the node branching factor.

Choosing the Right Structure

Pick a structure by asking what operations must be fast, how large the data may grow, and whether order or stability matters. A small decision guide and a cost table follow.

Following a practical selection checklist

If you mainly index by position, choose a dynamic array; if you mainly add and remove at the ends in FIFO order, choose a queue; if you need last-in first-out, choose a stack; if you need constant-time membership or counting, choose a dict; if you need ordered iteration and range queries at scale, choose a balanced tree; if you need repeated access to the smallest or largest item, choose a heap based priority queue.

Comparing common operations across structures

Use this summary to match operations to expected costs; all values are typical on mainstream implementations.

Combining structures to meet complex goals

Many robust systems blend structures: use a dict to map task id to a node in a balanced tree for ordered traversal; pair a heap with a dict of valid flags for lazy deletion; keep a dynamic array for dense data and a dict for sparse overrides; choose the simplest pair that gives the required guarantees and test with realistic sizes so that constants and cache locality do not surprise you.

# Lazy deletion: fast priority with membership checks
import heapq

h, alive = [], {}
def add(prio, key):
  heapq.heappush(h, (prio, key)); alive[key] = True
def pop_min():
  while h:
    p, k = heapq.heappop(h)
    if alive.pop(k, None):
      return (p, k)
  return None  # empty

add(5, "A"); add(1, "B"); add(1, "C")
alive["B"] = False  # mark invalid {…}
res = pop_min()     # returns (1, "C")

Data structures are the silent partners of algorithms; they turn abstract logic into fast, concrete action. The best designs rarely depend on one structure alone but on thoughtful combinations that complement each other’s strengths. When a system grows large, success often comes not from inventing a new structure but from choosing and composing the right existing ones. A well-balanced mix can turn an algorithm from theoretical elegance into practical speed, reliability, and clarity.