Data
Structures

What is a Data Structure?

A data structure is a specialized format for organizing, processing, retrieving, and storing data in a computer's memory so that it can be accessed and modified efficiently. Choosing the right data structure for a problem is often more impactful than the choice of algorithm — and the two are deeply intertwined.

Every data structure encodes two things: how data is laid out in memory and what operations it supports efficiently. Understanding both dimensions is what separates engineers who know syntax from engineers who write systems that scale.

The Four Core Operations

Every data structure is evaluated on how efficiently it supports these fundamental operations:

Arrays & Dynamic Arrays

An array is the most fundamental data structure: a contiguous block of memory holding elements of the same type. Because elements are stored side-by-side, you can compute the memory address of any element directly from its index in O(1) time — this is the defining property of arrays.

How Array Access Works in O(1)

The O(1) access time comes from simple arithmetic. If the array starts at memory address base and each element takes size bytes, then the address of element at index i is exactly base + i × size. This computation takes constant time regardless of the array's length — the CPU fetches it in a single memory operation.

# Static array address calculation
# base = 0x1000, element_size = 4 bytes (int32)
address(i) = 0x1000 + i * 4

# arr[3] → 0x1000 + 3 * 4 = 0x100C  → O(1)
# This is why arr[3] and arr[9999] cost the same!

int[] arr = {12, 34, 7, 99, 56, 21}
value = arr[3]   # → 99, one instruction

Dynamic Arrays — Amortized Growth

Static arrays have a fixed size. Dynamic arrays (Python list, Java ArrayList, C++ vector) automatically resize by allocating a new block of memory — typically twice the current size — when capacity is exceeded. This doubling strategy gives amortized O(1) appends: most appends are O(1), and the rare O(n) reallocation is spread across all the previous O(1) appends.

# Dynamic array growth pattern
# size:     1 → 2 → 4 → 8 → 16 → 32 …
# copies:   1   2   4   8   16   32 …
# Total copies for n inserts ≤ 2n → amortized O(1)

class DynamicArray:
    def __init__(self):
        self.data     = [None] * 1   # raw capacity
        self.size     = 0
        self.capacity = 1

    def append(self, val):
        if self.size == self.capacity:
            self._resize(self.capacity * 2)  # double!
        self.data[self.size] = val
        self.size += 1

    def _resize(self, new_cap):
        new_data = [None] * new_cap
        for i in range(self.size):
            new_data[i] = self.data[i]
        self.data, self.capacity = new_data, new_cap

Complexity Summary

Linked Lists

A linked list stores elements in nodes — each node holds a value and a pointer (reference) to the next node. Unlike arrays, nodes can live anywhere in memory; they are connected by pointers, not physical proximity. This makes insertion and deletion anywhere in the list O(1) given a pointer to the location, at the cost of O(1) random access.

Singly Linked List

Each node has a value and a single next pointer. Traversal is one-directional. Prepending is O(1); appending requires traversal to the tail (O(n)) unless a tail pointer is maintained.

class Node:
    def __init__(self, val):
        self.val  = val
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def prepend(self, val):   # O(1)
        node = Node(val)
        node.next = self.head
        self.head = node

    def delete(self, val):    # O(n) search + O(1) deletion
        prev, cur = None, self.head
        while cur:
            if cur.val == val:
                if prev: prev.next = cur.next
                else:    self.head = cur.next
                return
            prev, cur = cur, cur.next

Doubly Linked List

Each node carries both a next and a prev pointer, enabling backward traversal. This doubles memory usage per node but allows O(1) deletion when you already have a reference to the node (no need to find its predecessor).

Key Applications

Complexity Summary

Stacks, Queues, & Deques

Stacks and queues are abstract data types — they define behavior (which end you insert and remove from) rather than a specific memory layout. They can be implemented with arrays or linked lists; the choice of implementation affects constants but not the O(1) asymptotic complexity of their core operations.

Stack — LIFO

A stack supports exactly two primary operations: push (add to top) and pop (remove from top). Its LIFO order makes it the perfect model for any problem that requires "last action first undone" — including the actual call stack your programming language uses for function calls and recursion.

# Stack applications

# 1. Balanced parentheses checker
def is_balanced(s):
    stack, pairs = [], {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in '([{':     stack.append(ch)
        elif ch in pairs:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
    return not stack

# 2. Evaluate reverse Polish notation: "2 3 4 * +"
def eval_rpn(tokens):
    stack = []
    for t in tokens:
        if t in '+-*/':
            b, a = stack.pop(), stack.pop()
            stack.append(int(eval(f"{a}{t}{b}")))
        else:
            stack.append(int(t))
    return stack[0]   # → 14

Queue — FIFO

A queue supports enqueue (add to back) and dequeue (remove from front). It models real-world waiting lines. Implemented naively with an array, dequeue requires O(n) shifting — this is why the standard approach is a circular buffer (both enqueue and dequeue O(1)) or a doubly linked list.

from collections import deque

# Python's deque: O(1) append and popleft
q = deque()
q.append(1)     # enqueue → [1]
q.append(2)     # enqueue → [1, 2]
q.append(3)     # enqueue → [1, 2, 3]
q.popleft()     # dequeue → 1, queue is [2, 3]

# Queue powers BFS (Breadth-First Search)
def bfs(graph, start):
    visited, queue = {start}, deque([start])
    while queue:
        node = queue.popleft()
        for nbr in graph[node]:
            if nbr not in visited:
                visited.add(nbr)
                queue.append(nbr)

Priority Queue

A priority queue dequeues the highest-priority element first, not the oldest. Under the hood it is almost always implemented as a heap (covered in section 06). It powers Dijkstra's shortest-path algorithm, A* search, hospital triage systems, and OS process schedulers.

import heapq

# Python heapq: min-heap (negate for max-heap)
tasks = []
heapq.heappush(tasks, (3, "low priority"))
heapq.heappush(tasks, (1, "urgent"))
heapq.heappush(tasks, (2, "medium"))

heapq.heappop(tasks)  # → (1, "urgent")  ← smallest first
heapq.heappop(tasks)  # → (2, "medium")

Hash Tables

A hash table (hash map) maps keys to values in average O(1) time for get, set, and delete. It is the backbone of Python dictionaries, JavaScript objects, Java's HashMap, and Redis. The magic is a hash function that deterministically maps any key to an index in an underlying array.

The Hash Function

A hash function maps a key of arbitrary type and size to a fixed-range integer. A good hash function distributes keys uniformly across all buckets to minimize collisions. For strings, a common approach is to treat each character as a digit in a large base:

# Polynomial rolling hash (used in many languages)
def hash_string(key, table_size):
    h, base, mod = 0, 31, 10**9 + 9
    for ch in key:
        h = (h * base + ord(ch)) % mod
    return h % table_size

# hash("apple", 10) → some index in [0,9]
# Good hash: uniform, deterministic, fast
# Bad hash: always returns 0  (all collisions!)

Collision Resolution

Two keys can hash to the same bucket — this is a collision. There are two major strategies:

Load Factor & Rehashing

The load factor α = (number of entries) / (table size) governs performance. When α exceeds a threshold (typically 0.7–0.75), the table is rehashed: a new table of roughly twice the size is allocated and all entries are re-inserted. Like dynamic arrays, this is amortized O(1) per insert.

# Python dict internals (simplified)
# Load factor threshold: ~0.67
# Probing: compact hash tables (since Python 3.6)

d = {}
d["key"] = 42         # hash("key") % size → slot
d["key"]              # → 42   O(1) average
"key" in d           # → True  O(1) average
del d["key"]          # O(1) average

# Classic interview: word frequency count
freq = {}
for word in words:
    freq[word] = freq.get(word, 0) + 1

Complexity Summary

Trees & BSTs

A tree is a hierarchical data structure: a collection of nodes where each node has at most one parent and any number of children. The topmost node is the root; nodes with no children are leaves. Trees are ubiquitous — file systems, HTML DOMs, compiler ASTs, decision trees in ML, and database indexes all use them.

Binary Search Trees (BST)

A BST is a binary tree where every node's left subtree contains only values smaller than the node, and the right subtree only larger values. This property enables binary search on a dynamic dataset: at each node, you eliminate half the remaining tree.

class BST:
    class Node:
        def __init__(self, val):
            self.val   = val
            self.left  = self.right = None

    def insert(self, root, val):   # O(log n) avg, O(n) worst
        if not root: return self.Node(val)
        if   val < root.val: root.left  = self.insert(root.left,  val)
        elif val > root.val: root.right = self.insert(root.right, val)
        return root

    def search(self, root, val):   # O(log n) avg
        if not root or root.val == val: return root
        if val < root.val: return self.search(root.left,  val)
        else:              return self.search(root.right, val)

    def inorder(self, root):       # O(n) — yields sorted order!
        if root:
            yield from self.inorder(root.left)
            yield root.val
            yield from self.inorder(root.right)

Self-Balancing Trees

Tree Traversals

Heaps & Priority Queues

A heap is a complete binary tree (all levels fully filled except possibly the last, filled left to right) satisfying the heap property: in a max-heap, every parent is ≥ its children; in a min-heap, every parent is ≤ its children. This guarantee makes the root always the maximum (or minimum) element, accessible in O(1).

Heap Operations

The heap stores a complete binary tree in an array — no pointers needed. For a node at index i, its left child is at 2i + 1, right child at 2i + 2, and parent at ⌊(i-1)/2⌋. This layout is incredibly cache-friendly.

class MaxHeap:
    def __init__(self): self.h = []

    def push(self, val):               # O(log n)
        self.h.append(val)
        self._sift_up(len(self.h) - 1)

    def pop(self):                     # O(log n)
        self.h[0] = self.h[-1]         # put last at root
        self.h.pop()
        self._sift_down(0)
        return self.h[0]              # before sift, save it

    def _sift_up(self, i):
        parent = (i - 1) // 2
        while i > 0 and self.h[i] > self.h[parent]:
            self.h[i], self.h[parent] = self.h[parent], self.h[i]
            i, parent = parent, (parent - 1) // 2

    # Heapify: convert arbitrary array to heap in O(n)
    def heapify(self, arr):
        self.h = arr[:]
        for i in range(len(arr)//2, -1, -1):
            self._sift_down(i)          # O(n) total

Heap Sort

Heap sort uses the heap to sort in O(n log n) time with O(1) extra space — better space than merge sort, guaranteed O(n log n) unlike quick sort. It works by heapifying the array (O(n)), then repeatedly extracting the max and placing it at the end of the array.

Key Applications

Graphs — The Universal Model

A graph G = (V, E) is a set of vertices (nodes) V connected by edges E. Almost any relationship can be modeled as a graph: web pages and hyperlinks, people and friendships, cities and roads, dependencies between tasks, states in a finite automaton. Graphs are the most general and expressive data structure.

Graph Representations

The choice of representation affects the efficiency of every graph algorithm you run:

# Space: O(V + E)
graph = {
  'A': ['B', 'C'],
  'B': ['D'],
  'C': ['B', 'D'],
  'D': []
}
# Check if A→B: O(degree(A))
# Iterate A's neighbors: O(degree(A))

# Space: O(V²)  4×4 for 4 vertices
matrix = [
  [0,1,1,0],  # A→B, A→C
  [0,0,0,1],  # B→D
  [0,1,0,1],  # C→B, C→D
  [0,0,0,0],  # D: no edges
]
# Check if A→B: O(1) → matrix[0][1]

Types of Graphs

Union-Find (Disjoint Set)

A specialized structure for tracking connected components. Supports two operations: find (which component does this element belong to?) and union (merge two components). With path compression and union by rank, both operations run in near O(1) amortized (inverse Ackermann time — effectively constant).

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # parent[i] = i initially
        self.rank   = [0] * n

    def find(self, x):                 # O(α(n)) ≈ O(1)
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compress
        return self.parent[x]

    def union(self, x, y):             # O(α(n)) ≈ O(1)
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False     # already connected
        if self.rank[rx] < self.rank[ry]: rx, ry = ry, rx
        self.parent[ry] = rx           # union by rank
        if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1
        return True

# Used in Kruskal's MST: union edges greedily if no cycle forms

Tries — Prefix Trees

A trie (pronounced "try", from retrieval) is a tree where each node represents a character, and paths from root to nodes spell out strings. It is the ideal structure for any problem involving string prefixes: autocomplete, spell checking, IP routing tables, and word games.

Trie Operations

Every operation on a trie takes O(m) time where m is the length of the string — completely independent of how many strings are stored. This is the key advantage over hash tables for prefix operations.

class TrieNode:
    def __init__(self):
        self.children  = {}          # char → TrieNode
        self.is_end    = False       # marks end of a word

class Trie:
    def __init__(self): self.root = TrieNode()

    def insert(self, word):     # O(m)
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

    def search(self, word):     # O(m)
        node = self.root
        for ch in word:
            if ch not in node.children: return False
            node = node.children[ch]
        return node.is_end

    def starts_with(self, prefix):   # O(m) — key advantage!
        node = self.root
        for ch in prefix:
            if ch not in node.children: return False
            node = node.children[ch]
        return True

    def autocomplete(self, prefix):  # O(m + output)
        node = self.root
        for ch in prefix:
            if ch not in node.children: return []
            node = node.children[ch]
        results = []
        self._dfs(node, prefix, results)
        return results

    def _dfs(self, node, cur, results):
        if node.is_end: results.append(cur)
        for ch, child in node.children.items():
            self._dfs(child, cur + ch, results)

Master Comparison Table

Use this table to quickly identify the right data structure for a given operation requirement. Green = efficient, amber = acceptable, red = poor choice.

* Amortized    ** Given node reference    † Average case    m = string length

Decision Guide