数据结构完全参考

官方文档：https://wiki.python.org/moin/TimeComplexity
适用版本：Python 3.12（2026-05-07 核实）

时间复杂度速查表

按数据结构分组

* Python list 尾部 append 均摊 O(1)，头部 insert(0, x) 为 O(n)
** 需持有节点引用时才能 O(1)

数组与链表

对比表格

Python list 的底层实现

Python list 是动态数组（Dynamic Array）：

• 底层为 C 数组，存储对象指针
• 容量不足时按约 1.125 倍扩容（CPython 实现），重新分配内存并复制
• 扩容均摊后 append 为 O(1)
• list.insert(0, x) 需整体右移，为 O(n)
• list.pop() 尾部删除 O(1)，list.pop(0) 头部删除 O(n)

import sys

lst = []
for i in range(10):
    lst.append(i)
    # sys.getsizeof 返回当前分配的内存字节数
    print(f"len={len(lst)}, allocated_bytes={sys.getsizeof(lst)}")

推论：需要频繁头部操作时，用 collections.deque 替代 list。

单链表实现

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


class LinkedList:
    def __init__(self):
        self.dummy = ListNode(0)  # 哨兵节点，简化边界处理
        self.size = 0

    def append(self, val):
        node = self.dummy
        while node.next:
            node = node.next
        node.next = ListNode(val)
        self.size += 1

    def prepend(self, val):
        new_node = ListNode(val, self.dummy.next)
        self.dummy.next = new_node
        self.size += 1

    def delete(self, val):
        node = self.dummy
        while node.next:
            if node.next.val == val:
                node.next = node.next.next
                self.size -= 1
                return True
            node = node.next
        return False

    def to_list(self):
        result = []
        node = self.dummy.next
        while node:
            result.append(node.val)
            node = node.next
        return result

双链表实现

class DListNode:
    def __init__(self, val=0):
        self.val = val
        self.prev = None
        self.next = None


class DoublyLinkedList:
    def __init__(self):
        self.head = DListNode()  # 哨兵头
        self.tail = DListNode()  # 哨兵尾
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def _insert_after(self, node, val):
        new_node = DListNode(val)
        new_node.prev = node
        new_node.next = node.next
        node.next.prev = new_node
        node.next = new_node
        self.size += 1
        return new_node

    def append(self, val):
        return self._insert_after(self.tail.prev, val)

    def prepend(self, val):
        return self._insert_after(self.head, val)

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1

循环链表

循环链表将尾节点的 next 指向头节点。常见于约瑟夫环问题。使用时注意遍历终止条件应以初始节点为准，否则会无限循环。

栈与队列

栈

栈遵循 LIFO（后进先出）原则。

用 list 实现

stack = []
stack.append(1)   # 入栈
stack.append(2)
top = stack[-1]   # 查看栈顶：2
val = stack.pop() # 出栈：2

用 collections.deque 实现（线程安全版）

from collections import deque

stack = deque()
stack.append(1)
stack.append(2)
val = stack.pop()  # 从右侧弹出

deque 两端操作均为 O(1)，但随机访问为 O(n)。纯栈场景下 list 与 deque 性能接近，deque 更安全。

队列

队列遵循 FIFO（先进先出）原则。

collections.deque

from collections import deque

queue = deque()
queue.append(1)    # 入队（右侧）
queue.append(2)
val = queue.popleft()  # 出队（左侧）：1

queue.Queue（线程安全）

import queue

q = queue.Queue(maxsize=0)  # maxsize=0 表示无限容量
q.put(1)
q.put(2)
val = q.get()  # 阻塞等待

优先队列（heapq）

Python heapq 是最小堆。实现最大堆时将值取反。

import heapq

heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
print(heapq.heappop(heap))  # 1，最小值优先

# 最大堆：存入负值
max_heap = []
for val in [3, 1, 2]:
    heapq.heappush(max_heap, -val)
print(-heapq.heappop(max_heap))  # 3

单调栈

单调栈维护一个单调递增或递减的栈，用于求"下一个更大/更小元素"。

def next_greater_element(nums):
    """
    返回每个元素的下一个更大元素，不存在则为 -1。
    时间复杂度 O(n)，每个元素最多入栈/出栈一次。
    """
    n = len(nums)
    result = [-1] * n
    stack = []  # 存储索引，栈底到栈顶单调递减

    for i in range(n):
        # 当前元素比栈顶大，找到了栈顶的"下一个更大元素"
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)

    return result

单调队列

单调队列用于滑动窗口最值问题，队列中元素单调递减（求最大值）或单调递增（求最小值）。

from collections import deque

def sliding_window_max(nums, k):
    """
    返回每个长度为 k 的滑动窗口的最大值。
    时间复杂度 O(n)。
    """
    dq = deque()  # 存储索引，队列中对应的 nums 值单调递减
    result = []

    for i, num in enumerate(nums):
        # 移除队列中小于当前元素的索引（它们不可能是窗口最大值）
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)

        # 移除不在窗口内的队首元素
        if dq[0] < i - k + 1:
            dq.popleft()

        # 窗口已满
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

哈希表

Python dict 的底层

Python 3.6+ 的 dict 是有序（插入顺序）哈希表：

• 底层使用开放寻址法（Open Addressing）+ 紧凑数组
• 负载因子超过 2/3 时触发扩容（约 2 倍）
• 键必须是可哈希对象（实现了 __hash__ 和 __eq__）
• 查找均摊 O(1)，最坏 O(n)（哈希冲突严重时）

哈希冲突处理

collections.defaultdict

from collections import defaultdict

# 值默认为 list
graph = defaultdict(list)
graph['a'].append('b')  # 不存在 'a' 时自动创建空列表

# 值默认为 int（计数）
counter = defaultdict(int)
for char in "hello":
    counter[char] += 1

# 值默认为 set
adj = defaultdict(set)
adj['a'].add('b')

collections.Counter

from collections import Counter

c = Counter("abracadabra")
print(c.most_common(3))   # [('a', 5), ('b', 2), ('r', 2)]
print(c['a'])             # 5
print(c['z'])             # 0，不存在的键返回 0

# 支持加减运算
c2 = Counter("aab")
print(c + c2)             # 合并计数
print(c - c2)             # 差值（只保留正数）

collections.OrderedDict

Python 3.7+ 普通 dict 已保证插入顺序，OrderedDict 额外提供 move_to_end 方法，常用于实现 LRU 缓存。

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)  # 标记为最近使用
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)  # 删除最久未使用

树

二叉树表示

链式表示（面试常用）

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

数组表示（堆和完全二叉树）

对于索引从 1 开始的数组：

• 节点 i 的左子节点：2*i
• 节点 i 的右子节点：2*i + 1
• 节点 i 的父节点：i // 2

索引从 0 开始：

• 左子节点：2*i + 1
• 右子节点：2*i + 2
• 父节点：(i - 1) // 2

二叉搜索树（BST）

BST 性质：左子树所有值 < 根 < 右子树所有值，中序遍历结果有序。

class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        self.root = self._insert(self.root, val)

    def _insert(self, node, val):
        if not node:
            return TreeNode(val)
        if val < node.val:
            node.left = self._insert(node.left, val)
        elif val > node.val:
            node.right = self._insert(node.right, val)
        return node

    def search(self, val):
        node = self.root
        while node:
            if val == node.val:
                return True
            node = node.left if val < node.val else node.right
        return False

    def inorder(self):
        """中序遍历返回有序列表"""
        result = []
        def dfs(node):
            if not node:
                return
            dfs(node.left)
            result.append(node.val)
            dfs(node.right)
        dfs(self.root)
        return result

堆（Heap）

Python heapq 维护最小堆，参见优先队列（heapq）。

手动实现最大堆（用于理解原理）：

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

    def push(self, val):
        self.heap.append(val)
        self._sift_up(len(self.heap) - 1)

    def pop(self):
        if len(self.heap) == 1:
            return self.heap.pop()
        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._sift_down(0)
        return root

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

    def _sift_down(self, i):
        n = len(self.heap)
        while True:
            largest = i
            left, right = 2 * i + 1, 2 * i + 2
            if left < n and self.heap[left] > self.heap[largest]:
                largest = left
            if right < n and self.heap[right] > self.heap[largest]:
                largest = right
            if largest == i:
                break
            self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
            i = largest

Trie（前缀树）

class TrieNode:
    def __init__(self):
        self.children = {}   # char -> TrieNode
        self.is_end = False  # 是否是某个单词的结尾


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

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word):
        """完整单词查找"""
        node = self._find_node(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        """前缀查找"""
        return self._find_node(prefix) is not None

    def _find_node(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

并查集（Union-Find）

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # 初始时每个节点是自己的父节点
        self.rank = [0] * n           # 树的高度上界，用于按秩合并
        self.count = n                # 连通分量数

    def find(self, x):
        """路径压缩：递归后将路径上所有节点直接指向根"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        """按秩合并"""
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # 已在同一连通分量
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        self.count -= 1
        return True

    def connected(self, x, y):
        return self.find(x) == self.find(y)

路径压缩 + 按秩合并后，每次操作的均摊时间复杂度接近 O(1)（严格为 O(α(n))，α 为反阿克曼函数）。

图

邻接矩阵 vs 邻接表

# 邻接表（有向带权图）
from collections import defaultdict

graph = defaultdict(list)  # node -> [(neighbor, weight)]
graph[0].append((1, 5))
graph[0].append((2, 3))
graph[1].append((3, 2))

DFS 模板

# 递归 DFS
def dfs_recursive(graph, start):
    visited = set()

    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)

    dfs(start)
    return visited


# 迭代 DFS（使用显式栈，避免递归深度限制）
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)

    return visited

BFS 模板

from collections import deque

def bfs(graph, start):
    """
    BFS 层序遍历，同时记录每个节点的最短步数。
    """
    visited = {start}
    queue = deque([(start, 0)])  # (节点, 步数)
    dist = {start: 0}

    while queue:
        node, d = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                dist[neighbor] = d + 1
                queue.append((neighbor, d + 1))

    return dist

Dijkstra 最短路径

适用于非负权有向/无向图。时间复杂度 O((V + E) log V)。

import heapq
from collections import defaultdict

def dijkstra(graph, start, n):
    """
    graph: {node: [(neighbor, weight), ...]}
    返回从 start 到所有节点的最短距离。
    """
    dist = [float('inf')] * n
    dist[start] = 0
    heap = [(0, start)]  # (距离, 节点)

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue  # 已找到更短路径，跳过过时条目
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))

    return dist

拓扑排序

仅适用于有向无环图（DAG）。

Kahn 算法（BFS）

from collections import deque, defaultdict

def topological_sort_kahn(n, edges):
    """
    n: 节点数（0 到 n-1）
    edges: [(u, v), ...] 表示 u -> v
    返回拓扑序列，若存在环则返回空列表。
    """
    in_degree = [0] * n
    graph = defaultdict(list)

    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1

    queue = deque([i for i in range(n) if in_degree[i] == 0])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return order if len(order) == n else []  # 长度不足说明有环


def topological_sort_dfs(n, edges):
    """
    DFS 后序逆序得到拓扑序。
    """
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    visited = [0] * n  # 0: 未访问, 1: 访问中, 2: 已完成
    order = []
    has_cycle = [False]

    def dfs(node):
        if visited[node] == 1:
            has_cycle[0] = True
            return
        if visited[node] == 2:
            return
        visited[node] = 1
        for neighbor in graph[node]:
            dfs(neighbor)
        visited[node] = 2
        order.append(node)

    for i in range(n):
        if visited[i] == 0:
            dfs(i)

    if has_cycle[0]:
        return []
    return order[::-1]

踩坑与注意事项

• heapq 只提供最小堆。存储元组 (priority, item) 时，若 priority 相同会比较 item，确保 item 可比较或改用 (priority, counter, item) 加计数器。
• 递归 DFS 在节点数超过 Python 默认递归限制（1000）时会抛出 RecursionError，大图优先用迭代版本或用 sys.setrecursionlimit 调整。
• defaultdict 访问不存在的键会自动创建，序列化前注意清理，避免意外键出现在 JSON 输出中。
• 并查集的 find 带路径压缩时修改了 parent，多线程环境下需加锁。
• BST 退化为链表（全升序/全降序插入）时操作变为 O(n)，实际工程中用 AVL 树或红黑树（Python 标准库无内置，可用 sortedcontainers.SortedList）。

最佳实践

选数据结构前先问"瓶颈在哪"：写多读少 → 链表/堆；读多写少 → 数组/哈希表；有序范围查询 → 平衡 BST（sortedcontainers.SortedList）。用错结构导致的性能问题往往是量级差距，不是常数优化能弥补的。

Python 内置替代手写结构：优先用标准库而非手写：

• 队列 → collections.deque（O(1) 两端操作）
• 有序容器 → sortedcontainers.SortedList
• 优先队列 → heapq
• 计数器 → collections.Counter
• 双向映射 → dict + 反转 dict

并查集路径压缩与按秩合并同时开启：只开路径压缩均摊 O(α(n))，但最坏情况仍可能退化；同时开启按秩合并才能保证严格的逆阿克曼函数复杂度。

堆元素加懒删除标记替代直接删除：heapq 无法 O(log n) 删除任意元素。常见模式：标记为"已删除"，弹出时跳过：

import heapq

REMOVED = object()

def add_task(heap, entry_finder, task, priority):
    if task in entry_finder:
        entry_finder[task][-1] = REMOVED
    entry = [priority, task]
    entry_finder[task] = entry
    heapq.heappush(heap, entry)

def pop_task(heap, entry_finder):
    while heap:
        priority, task = heapq.heappop(heap)
        if task is not REMOVED:
            del entry_finder[task]
            return priority, task
    raise KeyError("pop from empty heap")

Trie 用 defaultdict 递归定义更简洁：避免手写节点类的样板代码：

from collections import defaultdict

def make_trie():
    return defaultdict(make_trie)

trie = make_trie()
# 插入 "cat"
trie['c']['a']['t']['#'] = True
# 查找前缀 "ca"
node = trie
for ch in "ca":
    if ch not in node:
        break
    node = node[ch]

常见陷阱

陷阱：栈/队列用 Python list 导致性能问题

现象： 用 list 的 pop(0) 模拟队列，数据量大时速度极慢。

原因： list.pop(0) 是 O(n) 操作，需要移动所有后续元素；队列操作应该是 O(1)。

解决： 用 collections.deque，appendleft/popleft 均为 O(1)；优先级队列用 heapq。

from collections import deque

q = deque()
q.append(1)      # 入队 O(1)
q.popleft()      # 出队 O(1)

# 错误：list 模拟队列
q = []
q.append(1)      # O(1)
q.pop(0)         # O(n)！数据量大时极慢

陷阱：二叉树递归缺少边界条件导致 RecursionError

现象： 递归遍历二叉树时，空节点处报 RecursionError: maximum recursion depth exceeded。

原因： 未处理 node is None 的基础情况，递归函数在空节点处继续调用自身，无限递归。

解决： 每个递归函数的第一行必须是空节点检查，立即返回基础值（None、0、[] 等）。

def max_depth(node):
    if node is None:   # 必须放第一行
        return 0
    return 1 + max(max_depth(node.left), max_depth(node.right))

adán：哈希表键为可变对象导致 KeyError

现象： 以 list 或 dict 作为字典键时，创建时正常，取值时报 TypeError: unhashable type: 'list'。

原因： Python 字典要求键必须是可哈希的（hashable），可变对象（list、dict、set）不可哈希，因为它们的内容可以改变，哈希值不固定。

解决： 将 list 键转为 tuple，将 dict 键转为 frozenset 或 JSON 字符串。

# 错误
d = {[1, 2]: 'value'}  # TypeError

# 正确：转为不可变类型
d = {(1, 2): 'value'}  # tuple 可哈希

参见

算法思路与模板