数据结构

数据结构基础¶

适用对象：

• 准备 LeetCode / 算法面试的人
• 已经会 Python 基础语法，但还没有形成“数据结构底层视角”的人

学习目标：

• 从“连续存储”和“链式存储”两个根视角理解常见数据结构
• 明白为什么会设计这种结构，而不是只记结论
• 理解时间复杂度和空间复杂度到底从哪里来
• 能在刷题时快速判断该用数组、链表、栈、队列、哈希表、树、堆还是图

写作原则：

• 以算法题和面试场景为主
• 示例代码全部使用 Python
• 优先讲清楚底层原理和常见用法
• 复杂工程细节可以跳过，不在这里展开

参考学习思想：

• Labuladong：数据结构基础
• Labuladong：复杂度基础

目录¶

1. 数据结构总览
2. 底层存储结构
3. 栈
4. 队列
5. 哈希表
6. 二叉树
7. 堆
8. 图
9. 数据结构与算法题

In [ ]:

from __future__ import annotations

from collections import deque
from typing import Any
import heapq
import sys

from __future__ import annotations from collections import deque from typing import Any import heapq import sys

1 数据结构总览¶

数据结构是什么：

• 数据结构是“如何存数据、如何访问数据、如何修改数据”的方式。
• 算法题本质上是在设计一套操作流程，而数据结构决定这些操作快不快。

为什么数据结构重要：

• 同一个题目，如果数据结构选错，复杂度经常会从 O(n) 变成 O(n^2)。
• 很多算法技巧并不是孤立的，它们都依赖某种数据结构。 例如：
  • 双指针依赖数组的连续访问
  • BFS 依赖队列
  • 括号匹配依赖栈
  • 两数之和依赖哈希表

时间复杂度与空间复杂度：

• 时间复杂度：输入规模增大时，操作次数如何变化。
• 空间复杂度：为了完成算法，需要额外开辟多少存储空间。
• 面试里更重要的是“复杂度为什么是这样”，而不是机械背答案。

最核心的学习思想：

• 数据结构的底层只有两种存储方式：
  • 连续存储：数组
  • 链式存储：链表
• 其他数据结构，本质上都可以看作对这两种存储方式的限制、扩展或组合。

从底层到上层的演化图：

数组 / 链表
   ↓
栈 / 队列
   ↓
哈希表
   ↓
树
   ↓
图

再换一种更实战的理解：

• 数组：我想按下标快速访问
• 链表：我想便宜地做插入和删除
• 栈：我只关心最后一个进入的元素
• 队列：我只关心第一个进入的元素
• 哈希表：我想按 key 快速找到 value
• 树：我想表达层次结构和递归结构
• 图：我想表达更一般的连接关系

2 底层存储结构¶

这一章是整份笔记的根。

如果不理解底层存储方式，后面所有复杂度都只能靠背。 如果理解了底层存储方式，很多复杂度就能自己推出来。

2.1 数组（连续存储）¶

数组的本质：

• 一段连续的内存空间。
• 每个元素大小相同。
• 可以通过“起始地址 + 偏移量”直接找到任意位置。

为什么数组支持 O(1) 随机访问：

• 假设起始地址是 base，每个元素大小是 size。
• 第 i 个元素地址就是 base + i * size。
• 所以访问 nums[i] 不需要从头走到尾，直接算地址即可。

为什么数组插入和删除成本高：

• 如果在中间插入一个元素，后面的元素通常都要整体后移。
• 如果在中间删除一个元素，后面的元素通常都要整体前移。
• 所以中间插入和删除的时间复杂度通常是 O(n)。

ASCII 示意图：

下标:   0    1    2    3
值:    10   20   30   40
内存: [10][20][30][40]
       ↑ 这些位置是连续的

动态数组为什么会出现：

• 普通数组长度固定。
• 但实际编程里，我们常常希望“先开一个空间，不够了再扩容”。
• 所以出现了动态数组。
• 动态数组的核心思想是：空间满了以后，申请一块更大的连续空间，把旧数据复制过去。

Python list 的刷题理解：

• 在算法题里，可以把 list 直接理解成动态数组。
• append 通常很快，因为是在尾部追加。
• 但扩容时需要整体复制，所以 append 是均摊 O(1)，不是绝对 O(1)。
• insert(i, x) 和 pop(0) 仍然可能是 O(n)，因为涉及搬移元素。

数组在算法题中的高频用途：

• 双指针
• 滑动窗口
• 前缀和
• 二分查找
• 原地修改

In [ ]:

class SimpleDynamicArray:
    def __init__(self, capacity: int = 2) -> None:
        self.capacity = max(2, capacity)
        self.size = 0
        self.data = [None] * self.capacity

    def __len__(self) -> int:
        return self.size

    def __getitem__(self, index: int) -> Any:
        if not 0 <= index < self.size:
            raise IndexError('index out of range')
        return self.data[index]

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

    def append(self, value: Any) -> None:
        if self.size == self.capacity:
            self._resize(self.capacity * 2)
        self.data[self.size] = value
        self.size += 1

    def insert(self, index: int, value: Any) -> None:
        if not 0 <= index <= self.size:
            raise IndexError('index out of range')
        if self.size == self.capacity:
            self._resize(self.capacity * 2)
        for i in range(self.size, index, -1):
            self.data[i] = self.data[i - 1]
        self.data[index] = value
        self.size += 1

    def pop(self, index: int = -1) -> Any:
        if self.size == 0:
            raise IndexError('pop from empty array')
        if index == -1:
            index = self.size - 1
        if not 0 <= index < self.size:
            raise IndexError('index out of range')
        value = self.data[index]
        for i in range(index, self.size - 1):
            self.data[i] = self.data[i + 1]
        self.data[self.size - 1] = None
        self.size -= 1
        return value

    def to_list(self) -> list[Any]:
        return self.data[: self.size]


arr = SimpleDynamicArray()
for x in [10, 20, 30]:
    arr.append(x)
arr.insert(1, 15)
removed = arr.pop(2)

{
    'array': arr.to_list(),
    'removed': removed,
    'length': len(arr),
    'capacity': arr.capacity,
    'random_access_example': arr[1],
}

class SimpleDynamicArray: def __init__(self, capacity: int = 2) -> None: self.capacity = max(2, capacity) self.size = 0 self.data = [None] * self.capacity def __len__(self) -> int: return self.size def __getitem__(self, index: int) -> Any: if not 0 <= index < self.size: raise IndexError('index out of range') return self.data[index] def _resize(self, new_capacity: int) -> None: new_data = [None] * new_capacity for i in range(self.size): new_data[i] = self.data[i] self.data = new_data self.capacity = new_capacity def append(self, value: Any) -> None: if self.size == self.capacity: self._resize(self.capacity * 2) self.data[self.size] = value self.size += 1 def insert(self, index: int, value: Any) -> None: if not 0 <= index <= self.size: raise IndexError('index out of range') if self.size == self.capacity: self._resize(self.capacity * 2) for i in range(self.size, index, -1): self.data[i] = self.data[i - 1] self.data[index] = value self.size += 1 def pop(self, index: int = -1) -> Any: if self.size == 0: raise IndexError('pop from empty array') if index == -1: index = self.size - 1 if not 0 <= index < self.size: raise IndexError('index out of range') value = self.data[index] for i in range(index, self.size - 1): self.data[i] = self.data[i + 1] self.data[self.size - 1] = None self.size -= 1 return value def to_list(self) -> list[Any]: return self.data[: self.size] arr = SimpleDynamicArray() for x in [10, 20, 30]: arr.append(x) arr.insert(1, 15) removed = arr.pop(2) { 'array': arr.to_list(), 'removed': removed, 'length': len(arr), 'capacity': arr.capacity, 'random_access_example': arr[1], }

In [ ]:

def observe_list_growth(n: int = 20) -> list[tuple[int, int]]:
    nums = []
    result = []
    last_size = sys.getsizeof(nums)
    for i in range(n):
        nums.append(i)
        current_size = sys.getsizeof(nums)
        if current_size != last_size:
            result.append((len(nums), current_size))
            last_size = current_size
    return result


observe_list_growth(50)[:8]

def observe_list_growth(n: int = 20) -> list[tuple[int, int]]: nums = [] result = [] last_size = sys.getsizeof(nums) for i in range(n): nums.append(i) current_size = sys.getsizeof(nums) if current_size != last_size: result.append((len(nums), current_size)) last_size = current_size return result observe_list_growth(50)[:8]

数组复杂度总结：

操作	时间复杂度	为什么
访问 nums[i]	O(1)	直接按下标算地址
修改 nums[i]	O(1)	直接覆盖
尾部追加 append	均摊 O(1)	大多数时候只在尾部写入
中间插入	O(n)	需要搬移后面的元素
中间删除	O(n)	需要搬移后面的元素

刷题提醒：

• Python 中绝大多数“数组题”，直接使用 list。
• nums.pop() 通常是 O(1)。
• nums.pop(0) 是 O(n)，因为它会整体搬移元素。

2.2 链表（链式存储）¶

链表的本质：

• 每个节点单独存储。
• 节点里保存值，以及指向其他节点的引用。
• 节点在内存里不要求连续。

为什么会设计链表：

• 数组的随机访问很快，但中间插入和删除很贵。
• 链表正好反过来：访问慢，但改指针便宜。

为什么链表插入和删除可以做到 O(1)：

• 如果你已经拿到了某个位置前面的节点，只需要改几根指针。
• 不需要像数组那样搬移大量元素。

但为什么链表查找是 O(n)：

• 因为不能像数组那样按下标直接跳过去。
• 必须从头节点开始，一个一个往后走。

单链表：

head -> [1 | next] -> [2 | next] -> [3 | next] -> None

双链表：

None <- [prev | 1 | next] <-> [prev | 2 | next] <-> [prev | 3 | next] -> None

循环链表：

• 最后一个节点不指向 None，而是回到头节点。
• 在算法题里不算最高频，但理解它有助于理解“环”的概念。

链表在算法题中的高频用途：

• 反转链表
• 合并有序链表
• 删除倒数第 k 个节点
• 快慢指针找环、找中点

In [ ]:

class SinglyListNode:
    def __init__(self, val: Any, next: 'SinglyListNode | None' = None) -> None:
        self.val = val
        self.next = next


class SinglyLinkedList:
    def __init__(self) -> None:
        self.dummy = SinglyListNode(0)
        self.size = 0

    def __len__(self) -> int:
        return self.size

    def _prev_node(self, index: int) -> SinglyListNode:
        if not 0 <= index <= self.size:
            raise IndexError('index out of range')
        prev = self.dummy
        for _ in range(index):
            prev = prev.next
        return prev

    def append(self, val: Any) -> None:
        self.insert(self.size, val)

    def prepend(self, val: Any) -> None:
        self.insert(0, val)

    def insert(self, index: int, val: Any) -> None:
        prev = self._prev_node(index)
        node = SinglyListNode(val, prev.next)
        prev.next = node
        self.size += 1

    def remove(self, index: int) -> Any:
        if not 0 <= index < self.size:
            raise IndexError('index out of range')
        prev = self._prev_node(index)
        target = prev.next
        prev.next = target.next
        self.size -= 1
        return target.val

    def get(self, index: int) -> Any:
        if not 0 <= index < self.size:
            raise IndexError('index out of range')
        cur = self.dummy.next
        for _ in range(index):
            cur = cur.next
        return cur.val

    def to_list(self) -> list[Any]:
        result = []
        cur = self.dummy.next
        while cur:
            result.append(cur.val)
            cur = cur.next
        return result


sll = SinglyLinkedList()
for x in [1, 2, 3]:
    sll.append(x)
sll.prepend(0)
sll.insert(2, 99)
removed = sll.remove(3)

{
    'singly_list': sll.to_list(),
    'removed': removed,
    'index_2_value': sll.get(2),
}

class SinglyListNode: def __init__(self, val: Any, next: 'SinglyListNode | None' = None) -> None: self.val = val self.next = next class SinglyLinkedList: def __init__(self) -> None: self.dummy = SinglyListNode(0) self.size = 0 def __len__(self) -> int: return self.size def _prev_node(self, index: int) -> SinglyListNode: if not 0 <= index <= self.size: raise IndexError('index out of range') prev = self.dummy for _ in range(index): prev = prev.next return prev def append(self, val: Any) -> None: self.insert(self.size, val) def prepend(self, val: Any) -> None: self.insert(0, val) def insert(self, index: int, val: Any) -> None: prev = self._prev_node(index) node = SinglyListNode(val, prev.next) prev.next = node self.size += 1 def remove(self, index: int) -> Any: if not 0 <= index < self.size: raise IndexError('index out of range') prev = self._prev_node(index) target = prev.next prev.next = target.next self.size -= 1 return target.val def get(self, index: int) -> Any: if not 0 <= index < self.size: raise IndexError('index out of range') cur = self.dummy.next for _ in range(index): cur = cur.next return cur.val def to_list(self) -> list[Any]: result = [] cur = self.dummy.next while cur: result.append(cur.val) cur = cur.next return result sll = SinglyLinkedList() for x in [1, 2, 3]: sll.append(x) sll.prepend(0) sll.insert(2, 99) removed = sll.remove(3) { 'singly_list': sll.to_list(), 'removed': removed, 'index_2_value': sll.get(2), }

In [ ]:

class DoublyListNode:
    def __init__(self, val: Any) -> None:
        self.val = val
        self.prev: 'DoublyListNode | None' = None
        self.next: 'DoublyListNode | None' = None


class DoublyLinkedList:
    def __init__(self) -> None:
        self.head = DoublyListNode(0)
        self.tail = DoublyListNode(0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def __len__(self) -> int:
        return self.size

    def _node_at(self, index: int) -> DoublyListNode:
        if not 0 <= index < self.size:
            raise IndexError('index out of range')
        if index < self.size // 2:
            cur = self.head.next
            for _ in range(index):
                cur = cur.next
        else:
            cur = self.tail.prev
            for _ in range(self.size - 1, index, -1):
                cur = cur.prev
        return cur

    def _insert_between(self, left: DoublyListNode, right: DoublyListNode, val: Any) -> None:
        node = DoublyListNode(val)
        node.prev = left
        node.next = right
        left.next = node
        right.prev = node
        self.size += 1

    def append(self, val: Any) -> None:
        self._insert_between(self.tail.prev, self.tail, val)

    def prepend(self, val: Any) -> None:
        self._insert_between(self.head, self.head.next, val)

    def insert(self, index: int, val: Any) -> None:
        if not 0 <= index <= self.size:
            raise IndexError('index out of range')
        if index == self.size:
            self.append(val)
            return
        right = self._node_at(index)
        left = right.prev
        self._insert_between(left, right, val)

    def remove(self, index: int) -> Any:
        node = self._node_at(index)
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1
        return node.val

    def to_list(self) -> list[Any]:
        result = []
        cur = self.head.next
        while cur is not self.tail:
            result.append(cur.val)
            cur = cur.next
        return result


dll = DoublyLinkedList()
for x in [10, 20, 30]:
    dll.append(x)
dll.prepend(5)
dll.insert(2, 15)
removed = dll.remove(1)

{
    'doubly_list': dll.to_list(),
    'removed': removed,
    'length': len(dll),
}

class DoublyListNode: def __init__(self, val: Any) -> None: self.val = val self.prev: 'DoublyListNode | None' = None self.next: 'DoublyListNode | None' = None class DoublyLinkedList: def __init__(self) -> None: self.head = DoublyListNode(0) self.tail = DoublyListNode(0) self.head.next = self.tail self.tail.prev = self.head self.size = 0 def __len__(self) -> int: return self.size def _node_at(self, index: int) -> DoublyListNode: if not 0 <= index < self.size: raise IndexError('index out of range') if index < self.size // 2: cur = self.head.next for _ in range(index): cur = cur.next else: cur = self.tail.prev for _ in range(self.size - 1, index, -1): cur = cur.prev return cur def _insert_between(self, left: DoublyListNode, right: DoublyListNode, val: Any) -> None: node = DoublyListNode(val) node.prev = left node.next = right left.next = node right.prev = node self.size += 1 def append(self, val: Any) -> None: self._insert_between(self.tail.prev, self.tail, val) def prepend(self, val: Any) -> None: self._insert_between(self.head, self.head.next, val) def insert(self, index: int, val: Any) -> None: if not 0 <= index <= self.size: raise IndexError('index out of range') if index == self.size: self.append(val) return right = self._node_at(index) left = right.prev self._insert_between(left, right, val) def remove(self, index: int) -> Any: node = self._node_at(index) node.prev.next = node.next node.next.prev = node.prev self.size -= 1 return node.val def to_list(self) -> list[Any]: result = [] cur = self.head.next while cur is not self.tail: result.append(cur.val) cur = cur.next return result dll = DoublyLinkedList() for x in [10, 20, 30]: dll.append(x) dll.prepend(5) dll.insert(2, 15) removed = dll.remove(1) { 'doubly_list': dll.to_list(), 'removed': removed, 'length': len(dll), }

链表复杂度总结：

操作	时间复杂度	为什么
按下标访问	O(n)	需要从头走到目标位置
头部插入	O(1)	只改指针
已知前驱节点后删除	O(1)	只改指针
查找某个值	O(n)	线性遍历

刷题提醒：

• “链表插入删除 O(1)”有前提：你已经拿到了目标位置附近的节点。
• 如果题目频繁要求随机访问第 k 个元素，链表通常不是好选择。

3 栈（Stack）¶

栈的本质：

• 栈不是新的底层存储方式。
• 它只是对数组或链表的一种“使用限制”。
• 只允许在同一端插入和删除。

栈的特点：

• LIFO：Last In, First Out，后进先出。

ASCII 示意图：

栈顶
 ↓
[3]
[2]
[1]

为什么会设计栈：

• 很多问题天然只关心“最近进入的元素”。
• 例如括号匹配、函数调用、撤销操作。

复杂度来源：

• 如果底层是数组，并且只在尾部 append / pop，那么操作是 O(1) 均摊。
• 如果底层是链表，并且只在头部操作，那么 push / pop 也是 O(1)。

栈在算法题中的高频用途：

• 括号匹配
• 单调栈
• 表达式求值
• 用显式栈模拟递归或 DFS

In [ ]:

class ArrayStack:
    def __init__(self) -> None:
        self.data: list[Any] = []

    def push(self, value: Any) -> None:
        self.data.append(value)

    def pop(self) -> Any:
        if not self.data:
            raise IndexError('pop from empty stack')
        return self.data.pop()

    def top(self) -> Any:
        if not self.data:
            raise IndexError('top from empty stack')
        return self.data[-1]

    def is_empty(self) -> bool:
        return not self.data


stack = ArrayStack()
for ch in ['a', 'b', 'c']:
    stack.push(ch)

{
    'top_before_pop': stack.top(),
    'popped': stack.pop(),
    'top_after_pop': stack.top(),
}

class ArrayStack: def __init__(self) -> None: self.data: list[Any] = [] def push(self, value: Any) -> None: self.data.append(value) def pop(self) -> Any: if not self.data: raise IndexError('pop from empty stack') return self.data.pop() def top(self) -> Any: if not self.data: raise IndexError('top from empty stack') return self.data[-1] def is_empty(self) -> bool: return not self.data stack = ArrayStack() for ch in ['a', 'b', 'c']: stack.push(ch) { 'top_before_pop': stack.top(), 'popped': stack.pop(), 'top_after_pop': stack.top(), }

In [ ]:

class StackNode:
    def __init__(self, val: Any, next: 'StackNode | None' = None) -> None:
        self.val = val
        self.next = next


class LinkedStack:
    def __init__(self) -> None:
        self.head: 'StackNode | None' = None

    def push(self, value: Any) -> None:
        self.head = StackNode(value, self.head)

    def pop(self) -> Any:
        if self.head is None:
            raise IndexError('pop from empty stack')
        value = self.head.val
        self.head = self.head.next
        return value

    def top(self) -> Any:
        if self.head is None:
            raise IndexError('top from empty stack')
        return self.head.val


linked_stack = LinkedStack()
for x in [1, 2, 3]:
    linked_stack.push(x)

{
    'top_before_pop': linked_stack.top(),
    'popped': linked_stack.pop(),
    'top_after_pop': linked_stack.top(),
}

class StackNode: def __init__(self, val: Any, next: 'StackNode | None' = None) -> None: self.val = val self.next = next class LinkedStack: def __init__(self) -> None: self.head: 'StackNode | None' = None def push(self, value: Any) -> None: self.head = StackNode(value, self.head) def pop(self) -> Any: if self.head is None: raise IndexError('pop from empty stack') value = self.head.val self.head = self.head.next return value def top(self) -> Any: if self.head is None: raise IndexError('top from empty stack') return self.head.val linked_stack = LinkedStack() for x in [1, 2, 3]: linked_stack.push(x) { 'top_before_pop': linked_stack.top(), 'popped': linked_stack.pop(), 'top_after_pop': linked_stack.top(), }

4 队列（Queue）¶

队列的本质：

• 队列也是一种限制结构。
• 常见规则是：尾部入队，头部出队。

队列的特点：

• FIFO：First In, First Out，先进先出。

ASCII 示意图：

队头 -> [1][2][3] <- 队尾

为什么会设计队列：

• 有些问题天然遵循“先来的先处理”。
• 例如 BFS、任务调度、消息处理。

为什么 deque 比 list 更适合做队列：

• list.append(x) 很快。
• 但 list.pop(0) 需要把后面所有元素整体前移，所以是 O(n)。
• collections.deque 为两端操作设计，append 和 popleft 都是 O(1)。
• 所以刷题里的队列几乎都优先用 deque。

队列在算法题中的高频用途：

• BFS
• 二叉树层序遍历
• 滑动窗口
• 拓扑排序

In [ ]:

class ListQueue:
    def __init__(self) -> None:
        self.data: list[Any] = []

    def enqueue(self, value: Any) -> None:
        self.data.append(value)

    def dequeue(self) -> Any:
        if not self.data:
            raise IndexError('dequeue from empty queue')
        return self.data.pop(0)

    def front(self) -> Any:
        if not self.data:
            raise IndexError('front from empty queue')
        return self.data[0]


q = ListQueue()
for x in [10, 20, 30]:
    q.enqueue(x)

{
    'front_before_dequeue': q.front(),
    'dequeued': q.dequeue(),
    'front_after_dequeue': q.front(),
}

class ListQueue: def __init__(self) -> None: self.data: list[Any] = [] def enqueue(self, value: Any) -> None: self.data.append(value) def dequeue(self) -> Any: if not self.data: raise IndexError('dequeue from empty queue') return self.data.pop(0) def front(self) -> Any: if not self.data: raise IndexError('front from empty queue') return self.data[0] q = ListQueue() for x in [10, 20, 30]: q.enqueue(x) { 'front_before_dequeue': q.front(), 'dequeued': q.dequeue(), 'front_after_dequeue': q.front(), }

In [ ]:

class DequeQueue:
    def __init__(self) -> None:
        self.data: deque[Any] = deque()

    def enqueue(self, value: Any) -> None:
        self.data.append(value)

    def dequeue(self) -> Any:
        if not self.data:
            raise IndexError('dequeue from empty queue')
        return self.data.popleft()

    def front(self) -> Any:
        if not self.data:
            raise IndexError('front from empty queue')
        return self.data[0]


q = DequeQueue()
for x in [10, 20, 30]:
    q.enqueue(x)

{
    'front_before_dequeue': q.front(),
    'dequeued': q.dequeue(),
    'front_after_dequeue': q.front(),
}

class DequeQueue: def __init__(self) -> None: self.data: deque[Any] = deque() def enqueue(self, value: Any) -> None: self.data.append(value) def dequeue(self) -> Any: if not self.data: raise IndexError('dequeue from empty queue') return self.data.popleft() def front(self) -> Any: if not self.data: raise IndexError('front from empty queue') return self.data[0] q = DequeQueue() for x in [10, 20, 30]: q.enqueue(x) { 'front_before_dequeue': q.front(), 'dequeued': q.dequeue(), 'front_after_dequeue': q.front(), }

5 哈希表（Hash Table）¶

哈希表的本质：

• 哈希表 = 数组 + 哈希函数。
• 哈希函数把 key 转成数组中的位置。

一个直观过程：

• 给定 key
• 计算 hash(key)
• 再映射到某个桶 index = hash(key) % capacity
• 到这个桶里找值

为什么哈希表平均是 O(1)：

• 如果哈希函数分布均匀，不同 key 会落到不同桶里。
• 那么查找时几乎像“直接定位”。
• 这就是平均 O(1) 的来源。

冲突是什么：

• 两个不同的 key 落到了同一个桶里。

解决冲突的两种经典方式：

• 拉链法：桶里挂一条链表或一个小数组。
• 开放地址法：冲突时继续向后探测空位。

ASCII 示意图：

buckets
0 -> []
1 -> [('apple', 3)] -> [('angle', 8)]
2 -> []
3 -> [('banana', 5)]

Python dict 的刷题理解：

• 在算法题里，把 dict 和 set 直接看作哈希表即可。
• 重点不是背 CPython 的底层细节，而是知道：
  • 平均查找 O(1)
  • 平均插入 O(1)
  • 平均删除 O(1)
  • 最坏情况下可能退化到 O(n)

哈希表在算法题中的高频用途：

• 两数之和
• 频次统计
• 去重
• 前缀和 + 哈希
• 滑动窗口计数

In [ ]:

class ChainingHashTable:
    def __init__(self, capacity: int = 8) -> None:
        self.capacity = max(4, capacity)
        self.size = 0
        self.buckets: list[list[list[Any]]] = [[] for _ in range(self.capacity)]

    def _index(self, key: Any) -> int:
        return hash(key) % self.capacity

    def _load_factor(self) -> float:
        return self.size / self.capacity

    def _resize(self, new_capacity: int) -> None:
        old_items = self.items()
        self.capacity = new_capacity
        self.size = 0
        self.buckets = [[] for _ in range(self.capacity)]
        for key, value in old_items:
            self.put(key, value)

    def put(self, key: Any, value: Any) -> None:
        bucket = self.buckets[self._index(key)]
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value
                return
        bucket.append([key, value])
        self.size += 1
        if self._load_factor() > 0.75:
            self._resize(self.capacity * 2)

    def get(self, key: Any, default: Any = None) -> Any:
        bucket = self.buckets[self._index(key)]
        for pair in bucket:
            if pair[0] == key:
                return pair[1]
        return default

    def remove(self, key: Any) -> Any:
        bucket = self.buckets[self._index(key)]
        for i, pair in enumerate(bucket):
            if pair[0] == key:
                self.size -= 1
                return bucket.pop(i)[1]
        raise KeyError(key)

    def items(self) -> list[tuple[Any, Any]]:
        result = []
        for bucket in self.buckets:
            for key, value in bucket:
                result.append((key, value))
        return result


table = ChainingHashTable()
table.put('alice', 3)
table.put('bob', 5)
table.put('alice', 8)
removed = table.remove('bob')

{
    'items': sorted(table.items()),
    'removed': removed,
    'get_alice': table.get('alice'),
}

class ChainingHashTable: def __init__(self, capacity: int = 8) -> None: self.capacity = max(4, capacity) self.size = 0 self.buckets: list[list[list[Any]]] = [[] for _ in range(self.capacity)] def _index(self, key: Any) -> int: return hash(key) % self.capacity def _load_factor(self) -> float: return self.size / self.capacity def _resize(self, new_capacity: int) -> None: old_items = self.items() self.capacity = new_capacity self.size = 0 self.buckets = [[] for _ in range(self.capacity)] for key, value in old_items: self.put(key, value) def put(self, key: Any, value: Any) -> None: bucket = self.buckets[self._index(key)] for pair in bucket: if pair[0] == key: pair[1] = value return bucket.append([key, value]) self.size += 1 if self._load_factor() > 0.75: self._resize(self.capacity * 2) def get(self, key: Any, default: Any = None) -> Any: bucket = self.buckets[self._index(key)] for pair in bucket: if pair[0] == key: return pair[1] return default def remove(self, key: Any) -> Any: bucket = self.buckets[self._index(key)] for i, pair in enumerate(bucket): if pair[0] == key: self.size -= 1 return bucket.pop(i)[1] raise KeyError(key) def items(self) -> list[tuple[Any, Any]]: result = [] for bucket in self.buckets: for key, value in bucket: result.append((key, value)) return result table = ChainingHashTable() table.put('alice', 3) table.put('bob', 5) table.put('alice', 8) removed = table.remove('bob') { 'items': sorted(table.items()), 'removed': removed, 'get_alice': table.get('alice'), }

In [ ]:

nums = [1, 2, 2, 3, 3, 3]

freq = {}
for x in nums:
    freq[x] = freq.get(x, 0) + 1

unique = set(nums)

{
    'frequency': freq,
    'unique_values': unique,
    'contains_2': 2 in unique,
}

nums = [1, 2, 2, 3, 3, 3] freq = {} for x in nums: freq[x] = freq.get(x, 0) + 1 unique = set(nums) { 'frequency': freq, 'unique_values': unique, 'contains_2': 2 in unique, }

哈希表复杂度总结：

操作	平均复杂度	最坏复杂度	为什么
查找	O(1)	O(n)	分布均匀时接近直接定位
插入	O(1)	O(n)	冲突严重或扩容时变慢
删除	O(1)	O(n)	同上

刷题提醒：

• 只要题目里出现“是否存在”“出现次数”“映射关系”，优先想到哈希表。
• Python 刷题里，dict 和 set 基本是默认答案。

6 二叉树¶

二叉树的本质：

• 每个节点最多有两个孩子：left 和 right。
• 这种结构天然适合递归思考。

ASCII 示意图：

        1
      /                2     3
    /            4   5

为什么会设计树：

• 有些数据天然就是层次结构。
• 例如组织结构、表达式、搜索结构、递归拆分结构。

为什么树题常常可以递归：

• 因为一棵树由“根节点 + 左子树 + 右子树”组成。
• 左右子树本身又是同样的问题。

常见遍历方式：

• 前序遍历：根 -> 左 -> 右
• 中序遍历：左 -> 根 -> 右
• 后序遍历：左 -> 右 -> 根
• 层序遍历：一层一层访问，通常借助队列

复杂度来源：

• 遍历时每个节点最多访问一次，所以时间复杂度通常是 O(n)。
• 递归的额外空间通常和树高有关。
  • 平衡树：O(log n)
  • 链状树：O(n)

二叉树在算法题中的高频用途：

• 各种遍历
• 路径和
• 最近公共祖先
• 二叉搜索树性质利用
• 树形 DP

In [ ]:

class TreeNode:
    def __init__(
        self,
        val: Any,
        left: 'TreeNode | None' = None,
        right: 'TreeNode | None' = None,
    ) -> None:
        self.val = val
        self.left = left
        self.right = right


def preorder(root: TreeNode | None) -> list[Any]:
    if root is None:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)


def inorder(root: TreeNode | None) -> list[Any]:
    if root is None:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)


def postorder(root: TreeNode | None) -> list[Any]:
    if root is None:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]


def level_order(root: TreeNode | None) -> list[list[Any]]:
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result


root = TreeNode(
    1,
    left=TreeNode(2, TreeNode(4), TreeNode(5)),
    right=TreeNode(3),
)

{
    'preorder': preorder(root),
    'inorder': inorder(root),
    'postorder': postorder(root),
    'level_order': level_order(root),
}

class TreeNode: def __init__( self, val: Any, left: 'TreeNode | None' = None, right: 'TreeNode | None' = None, ) -> None: self.val = val self.left = left self.right = right def preorder(root: TreeNode | None) -> list[Any]: if root is None: return [] return [root.val] + preorder(root.left) + preorder(root.right) def inorder(root: TreeNode | None) -> list[Any]: if root is None: return [] return inorder(root.left) + [root.val] + inorder(root.right) def postorder(root: TreeNode | None) -> list[Any]: if root is None: return [] return postorder(root.left) + postorder(root.right) + [root.val] def level_order(root: TreeNode | None) -> list[list[Any]]: if root is None: return [] result = [] queue = deque([root]) while queue: level_size = len(queue) level = [] for _ in range(level_size): node = queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result root = TreeNode( 1, left=TreeNode(2, TreeNode(4), TreeNode(5)), right=TreeNode(3), ) { 'preorder': preorder(root), 'inorder': inorder(root), 'postorder': postorder(root), 'level_order': level_order(root), }

7 堆（Heap / 优先队列）¶

堆的本质：

• 堆 = 完全二叉树 + 数组存储。
• 这句话非常重要，因为堆虽然看起来是树，但底层通常直接放在数组中。

为什么数组能存完全二叉树：

• 完全二叉树按层从左到右排列得很紧凑。
• 所以可以直接通过下标推出父子关系。
• 对于下标 i：
  • 左孩子：2 * i + 1
  • 右孩子：2 * i + 2
  • 父节点：(i - 1) // 2

最小堆和最大堆：

• 最小堆：父节点值 <= 子节点值
• 最大堆：父节点值 >= 子节点值

为什么堆的插入和删除是 O(log n)：

• 插入后需要向上调整。
• 删除堆顶后需要向下调整。
• 调整的路径长度就是树高。
• 完全二叉树的高度是 O(log n)。

ASCII 示意图：

数组: [1, 3, 5, 7, 9]

        1
      /                3     5
    /            7   9

堆在算法题中的高频用途：

• Top K
• 合并 K 个有序链表
• 数据流第 k 大
• 每次快速取最小值或最大值

In [ ]:

nums = [5, 1, 7, 2, 9]

min_heap: list[int] = []
for x in nums:
    heapq.heappush(min_heap, x)

smallest_before = min_heap[0]
popped_smallest = heapq.heappop(min_heap)

max_heap: list[int] = []
for x in nums:
    heapq.heappush(max_heap, -x)

largest_before = -max_heap[0]
popped_largest = -heapq.heappop(max_heap)

{
    'min_heap_after_pop': min_heap,
    'smallest_before': smallest_before,
    'popped_smallest': popped_smallest,
    'largest_before': largest_before,
    'popped_largest': popped_largest,
}

nums = [5, 1, 7, 2, 9] min_heap: list[int] = [] for x in nums: heapq.heappush(min_heap, x) smallest_before = min_heap[0] popped_smallest = heapq.heappop(min_heap) max_heap: list[int] = [] for x in nums: heapq.heappush(max_heap, -x) largest_before = -max_heap[0] popped_largest = -heapq.heappop(max_heap) { 'min_heap_after_pop': min_heap, 'smallest_before': smallest_before, 'popped_smallest': popped_smallest, 'largest_before': largest_before, 'popped_largest': popped_largest, }

堆复杂度总结：

操作	时间复杂度	为什么
查看堆顶	O(1)	数组下标 0
插入	O(log n)	沿树高向上调整
删除堆顶	O(log n)	沿树高向下调整
建堆	O(n)	自底向上调整

刷题提醒：

• Python 的 heapq 默认是最小堆。
• 需要最大堆时，常用“存负数”的技巧。
• 堆不是有序数组，它只保证堆顶最值。

8 图（Graph）¶

图的本质：

• 图由顶点（vertex）和边（edge）组成。
• 它是比树更一般的连接结构。
• 树可以看作一种特殊的图。

图的两种常见存储方式：

• 邻接矩阵
• 邻接表

邻接矩阵：

• 用二维数组表示边是否存在。
• 查询两点是否相连很快，是 O(1)。
• 但空间复杂度是 O(V^2)，稀疏图会浪费空间。

邻接表：

• 每个点维护一个列表，记录和它相连的点。
• 空间复杂度通常是 O(V + E)。
• 算法题里更常用。

ASCII 示意图：

A -- B
|    |
C -- D

图的两种基本遍历：

• DFS：深度优先搜索
• BFS：广度优先搜索

为什么 DFS / BFS 常见复杂度是 O(V + E)：

• 每个点最多访问一次。
• 每条边最多检查一次。

图在算法题中的高频用途：

• 岛屿问题
• 连通分量
• 最短路径
• 拓扑排序
• 课程表

In [ ]:

graph_adj_list = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C'],
}

vertices = ['A', 'B', 'C', 'D']
graph_adj_matrix = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 1],
    [0, 1, 1, 0],
]


def dfs(graph: dict[str, list[str]], start: str) -> list[str]:
    visited = set()
    order = []

    def traverse(node: str) -> None:
        visited.add(node)
        order.append(node)
        for nxt in graph[node]:
            if nxt not in visited:
                traverse(nxt)

    traverse(start)
    return order


def bfs(graph: dict[str, list[str]], start: str) -> list[str]:
    visited = {start}
    order = []
    queue = deque([start])
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            if nxt not in visited:
                visited.add(nxt)
                queue.append(nxt)
    return order


{
    'adjacency_matrix_vertices': vertices,
    'adjacency_matrix': graph_adj_matrix,
    'dfs_from_A': dfs(graph_adj_list, 'A'),
    'bfs_from_A': bfs(graph_adj_list, 'A'),
}

graph_adj_list = { 'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D'], 'D': ['B', 'C'], } vertices = ['A', 'B', 'C', 'D'] graph_adj_matrix = [ [0, 1, 1, 0], [1, 0, 0, 1], [1, 0, 0, 1], [0, 1, 1, 0], ] def dfs(graph: dict[str, list[str]], start: str) -> list[str]: visited = set() order = [] def traverse(node: str) -> None: visited.add(node) order.append(node) for nxt in graph[node]: if nxt not in visited: traverse(nxt) traverse(start) return order def bfs(graph: dict[str, list[str]], start: str) -> list[str]: visited = {start} order = [] queue = deque([start]) while queue: node = queue.popleft() order.append(node) for nxt in graph[node]: if nxt not in visited: visited.add(nxt) queue.append(nxt) return order { 'adjacency_matrix_vertices': vertices, 'adjacency_matrix': graph_adj_matrix, 'dfs_from_A': dfs(graph_adj_list, 'A'), 'bfs_from_A': bfs(graph_adj_list, 'A'), }

9 数据结构与算法题¶

刷题最常用的数据结构总结：

数据结构	典型题型	你应该想到的关键词
数组	双指针、滑动窗口、前缀和、二分	下标、连续区间、原地修改
链表	反转、合并、删除节点、找环	指针、虚拟头结点、快慢指针
栈	括号匹配、单调栈、表达式	后进先出、最近元素
队列	BFS、层序遍历、滑窗队列	先进先出、按层扩散
哈希表	两数之和、计数、去重	存在性、频次、映射
树	DFS、路径和、BST、LCA	递归、子树、层序
堆	Top K、数据流最值	动态维护最值
图	连通性、最短路、拓扑排序	点、边、遍历

面试里的一个快速判断模板：

• 需要 O(1) 按位置访问：数组
• 需要频繁插入删除并愿意牺牲随机访问：链表
• 需要只处理“最近加入”的元素：栈
• 需要只处理“最早加入”的元素：队列
• 需要按 key 快速查询：哈希表
• 需要表达父子层次和递归结构：树
• 需要动态维护最值：堆
• 需要处理点与点之间的连接关系：图

最后再回到这份笔记最重要的一句话：

• 不要把数据结构看成一堆分散的名词。
• 它们大多都能追溯到两种底层存储方式：数组和链表。
• 复杂度也不是凭空来的，而是由底层存储方式和具体操作共同决定的。

一句话总结：

• 数组快在访问，慢在中间改动。
• 链表快在改指针，慢在查找定位。
• 其他结构，都是围绕这两点做限制、优化或组合。